fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #ifdef getchar
  4. #undef getchar
  5. #endif
  6. #define getchar() (*_pinp?*_pinp++:(_inp[fread(_pinp=_inp, 1, 4096, stdin)]='\0', *_pinp++))
  7. char _inp[4097], *_pinp=_inp;
  8. #define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
  9. char _;
  10. #ifdef putchar
  11. #undef putchar
  12. #endif
  13. #define putchar(x) (*_pout++=(x), (_pout==_eout?(fwrite(_pout=_out, 1, 4096, stdout)):0))
  14. #define flush() fwrite(_out, 1, _pout-_out, stdout)
  15. char _out[4097], *_eout=_out+4096, *_pout=_out;
  16. #define print(x) do{if(!x)putchar('0');else{x=x<0?(putchar('-'), -x):x;for(;x;x/=10)*_p++='0'+x%10;do putchar(*--_p);while(_p!=_buf);}}while(0)
  17. char _buf[20], *_p=_buf;
  18.  
  19. using namespace std;
  20.  
  21. int N, M;
  22. int A[100001];
  23. enum {L, R};
  24. struct node
  25. {
  26.     node *link[2];
  27.     long long val, add, mul;
  28. } pool[8000000], *nextpool=pool, *nil, *tree[100001];
  29.  
  30. inline node* alloc(node *orig)
  31. {
  32.     *nextpool=*orig;
  33.     return nextpool++;
  34. }
  35.  
  36. node* init(int begin, int end)
  37. {
  38.     node *root=nextpool++;
  39.     int mid=(begin+end)/2;
  40.     if(begin==end)
  41.         root->link[L]=root->link[R]=nil;
  42.     else
  43.     {
  44.         root->link[L]=init(begin, mid);
  45.         root->link[R]=init(mid+1, end);
  46.     }
  47.     return root;
  48. }
  49.  
  50. inline void down(node *root, int begin, int end)
  51. {
  52.     if(root->add!=0 || root->mul!=0)
  53.     {
  54.         int mid=(begin+end)/2;
  55.         root->link[L]=alloc(root->link[L]);
  56.         if(begin==mid)
  57.             root->link[L]->val+=root->add*(mid-begin+1)+1LL*(mid-begin)*(mid-begin+1)/2*root->mul;
  58.         root->link[L]->add+=root->add;
  59.         root->link[L]->mul+=root->mul;
  60.         root->link[R]=alloc(root->link[R]);
  61.         if(mid+1==end)
  62.             root->link[R]->val+=root->add*(end-mid)+(1LL*(end-begin)*(end-begin+1)-1LL*(mid-begin)*(mid-begin+1))/2*root->mul;
  63.         root->link[R]->add+=root->add+1LL*(mid-begin+1)*root->mul;
  64.         root->link[R]->mul+=root->mul;
  65.         root->add=root->mul=0;
  66.     }
  67. }
  68.  
  69. node* update(node *root, int begin, int end, int i, int j, int x, int y)
  70. {
  71.     if(j<begin || end<i)
  72.         return root;
  73.     root=alloc(root);
  74.     if(i<=begin && end<=j)
  75.     {
  76.         if(begin==end)
  77.             root->val+=1LL*x*(end-begin+1)+(1LL*(end-i)*(end-i+1)-1LL*(begin-i-1)*(begin-i))/2*y;
  78.         root->add+=x+1LL*(begin-i)*y;
  79.         root->mul+=y;
  80.     }
  81.     else
  82.     {
  83.         down(root, begin, end);
  84.         int mid=(begin+end)/2;
  85.         root->link[L]=update(root->link[L], begin, mid, i, j, x, y);
  86.         root->link[R]=update(root->link[R], mid+1, end, i, j, x, y);
  87.         //root->val=root->link[L]->val+root->link[R]->val;
  88.     }
  89.     return root;
  90. }
  91.  
  92. long long query(node *root, int begin, int end, int x)
  93. {
  94.     root=alloc(root);
  95.     while(begin!=end)
  96.     {
  97.         int mid=(begin+end)/2;
  98.         if(mid>=x)
  99.         {
  100.             root->link[L]=alloc(root->link[L]);
  101.             if(root->add!=0 || root->mul!=0)
  102.             {
  103.                 if(begin==mid)
  104.                     root->link[L]->val+=root->add*(mid-begin+1)+1LL*(mid-begin)*(mid-begin+1)/2*root->mul;
  105.                 root->link[L]->add+=root->add;
  106.                 root->link[L]->mul+=root->mul;
  107.                 root->add=root->mul=0;
  108.             }
  109.             end=mid;
  110.             root=root->link[L];
  111.         }
  112.         else
  113.         {
  114.             root->link[R]=alloc(root->link[R]);
  115.             if(root->add!=0 || root->mul!=0)
  116.             {
  117.                 if(mid+1==end)
  118.                     root->link[R]->val+=root->add*(end-mid)+(1LL*(end-begin)*(end-begin+1)-1LL*(mid-begin)*(mid-begin+1))/2*root->mul;
  119.                 root->link[R]->add+=root->add+1LL*(mid-begin+1)*root->mul;
  120.                 root->link[R]->mul+=root->mul;
  121.                 root->add=root->mul=0;
  122.             }
  123.             begin=mid+1;
  124.             root=root->link[R];
  125.         }
  126.     }
  127.     return root->val;
  128. }
  129.  
  130. int main()
  131. {
  132.     nil=nextpool++;
  133.     nil->link[L]=nil->link[R]=nil;
  134.     scan(N);
  135.     for(int i=1; i<=N; i++)
  136.         scan(A[i]);
  137.     int a, b, c, d;
  138.     for(int i=1; i<=N; i++)
  139.     {
  140.         scan(a);
  141.         A[i]=a-A[i];
  142.     }
  143.     scan(M);
  144.     tree[0]=init(1, N);
  145.     for(int i=1; i<=M; i++)
  146.     {
  147.         scan(a);
  148.         scan(b);
  149.         scan(c);
  150.         scan(d);
  151.         tree[i]=update(tree[i-1], 1, N, a, b, c, d);
  152.     }
  153.     node *remember=nextpool;
  154.     for(int i=1; i<=N; i++)
  155.     {
  156.         nextpool=remember;
  157.         int lo=0, mid, hi=M+1;
  158.         while(lo<hi)
  159.         {
  160.             mid=(lo+hi)/2;
  161.             if(query(tree[mid], 1, N, i)>=A[i])
  162.                 hi=mid;
  163.             else
  164.                 lo=mid+1;
  165.         }
  166.         int v=lo==M+1?-1:lo;
  167.         print(v);
  168.         putchar(" \n"[i==N]);
  169.     }
  170.     flush();
  171.     return 0;
  172. }
Success #stdin #stdout 0s 254080KB
comments (?)
stdin
copy 
5
5 4 4 2 1
7 7 4 7 7
3
1 2 2 0
2 5 1 1
3 4 2 2
stdout
copy 
1 2 0 3 -1
https://ideone.com/01kXO2
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!