fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define el "\n"
  13. #define MASK(i) (1LL<<(i))
  14. #define BIT(i,j) (((i)>>(j))&1)
  15. #define TIME 1.0*clock()/CLOCKS_PER_SEC
  16.  
  17. const ll MAX=2e3+3,MOD=1e9+7;
  18. int n;
  19. struct Point
  20. {
  21.     int x,y;
  22.     bool operator <(const Point &other) const
  23.     {
  24.         if(x!=other.x) return x>other.x;
  25.         return y>other.y;
  26.     }
  27. } p[MAX];
  28. vector<int> v;
  29. int getVal(int val)
  30. {
  31.     return lower_bound(v.begin(),v.end(),val)-v.begin()+1;
  32. }
  33. void pre()
  34. {
  35.     sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
  36.     foru(i,1,n)
  37.     {
  38.         p[i].x=getVal(p[i].x);
  39.         p[i].y=getVal(p[i].y);
  40.     }
  41.     sort(p+1,p+n+1);
  42. //    foru(i,1,n) cout<<p[i].x<<' '<<p[i].y<<el;
  43. }
  44. ll fw[2*MAX][MAX];
  45. void update(int pos, int pos1, ll val)
  46. {
  47.     int j=pos1;
  48.     for(int i=pos; i<2*MAX; i+=i&(-i))
  49.     {
  50. //        for(int j=pos1; j<2*MAX; j+=j&(-j))
  51. //        {
  52.             fw[i][j]=(fw[i][j]+val)%MOD;
  53. //        }
  54.     }
  55. }
  56. ll query(int pos, int pos1)
  57. {
  58.     ll ans=0;
  59.     int j=pos1;
  60.     for(int i=pos; i>0; i-=i&(-i))
  61.     {
  62. //        for(int j=pos1; j>0; j-=j&(-j))
  63. //        {
  64.             ans=(ans+fw[i][j])%MOD;
  65. //        }
  66.     }
  67.     return ans;
  68. }
  69.  
  70. void calc()
  71. {
  72.     int mx=0;
  73.     foru(i,1,n)
  74.     {
  75.         mx=max(mx,p[i].y);
  76.         update(p[i].y,1,1);
  77.         foru(l,2,n)
  78.         {
  79.             ll q=query(p[i].y-1,l-1);
  80. //            cout<<i<<' '<<l<<' '<<q<<el;
  81.             update(p[i].y,l,q);
  82.         }
  83. //        cout<<el;
  84.     }
  85.     foru(l,1,n)
  86.     {
  87.         cout<<query(mx,l)<<' ';
  88.     }
  89. }
  90.  
  91. int main()
  92. {
  93.     fastio
  94.     if(fopen(FILE ".inp","r"))
  95.     {
  96.         freopen(FILE ".inp","r",stdin);
  97.         freopen(FILE ".out","w",stdout);
  98.     }
  99.     cin>>n;
  100.     foru(i,1,n) cin>>p[i].x;
  101.     foru(i,1,n)
  102.     {
  103.         cin>>p[i].y;
  104.         v.pb(p[i].x);
  105.         v.pb(p[i].y);
  106.     }
  107.     pre();
  108.     calc();
  109.  
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AjrjYS
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!