fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define X first
  6. #define Y second
  7. #define INPUT freopen("draft.inp","r",stdin)
  8. #define OUTPUT freopen("draft.out","w",stdout)
  9. #define FOR(i,l,r) for(auto i=l;i<=r;i++)
  10. #define REP(i,l,r) for(auto i=l;i<r;i++)
  11. #define FORD(i,l,r) for(auto i=l;i>=r;i--)
  12. #define REPD(i,l,r) for(auto i=l;i>r;i--)
  13. #define ENDL printf("\n")
  14. #define debug 1
  15.  
  16. typedef long long ll;
  17. typedef pair<int,int> ii;
  18.  
  19. const int inf=1e9;
  20. const int MOD=1e9+7;
  21. const double PI=3.14159265359;
  22. const int N=1e5+10;
  23.  
  24.  
  25. template <class T> bool minimize(T &x,T y){
  26.     if (x>y) x=y;else return 0;
  27.     return 1;
  28. }
  29. template <class T> bool maximize(T &x,T y){
  30.     if (x<y) x=y;else return 0;
  31.     return 1;
  32. }
  33.  
  34. ll S[N<<2],sum[N<<2][2];
  35. int laz[N<<2][2],c[N<<2];
  36. ii h[N<<2][2],ma[N<<2][2],mi[N<<2][2];
  37.  
  38. int n,m,a[N][2],gold[2],q[N][4];
  39. void lazyupdate(int node,int L,int R){
  40.     if (!c[node]) return;
  41.     FOR(type,0,1) if (h[node][type].Y){
  42.         ma[node][type].X=mi[node][type].X=h[node][type].X;
  43.         sum[node][type]=1LL*h[node][type].X*c[node];
  44.         S[node]=1LL*h[node][type].X*sum[node][type^1];
  45.         if (L<R){
  46.             h[node*2][type]=h[node*2+1][type]=h[node][type];
  47.             laz[node*2][type]=laz[node*2+1][type]=0;
  48.         }
  49.         h[node][type]=ii(0,0);
  50.     }
  51.     S[node]+=sum[node][1]*laz[node][0]+sum[node][0]*laz[node][1]+1LL*laz[node][0]*laz[node][1]*c[node];
  52.     FOR(i,0,1) if (laz[node][i]){
  53.         sum[node][i]+=1LL*laz[node][i]*c[node];
  54.         ma[node][i].X+=laz[node][i];
  55.         mi[node][i].X+=laz[node][i];
  56.         if (L<R){
  57.             laz[node*2][i]+=laz[node][i];
  58.             laz[node*2+1][i]+=laz[node][i];
  59.         }
  60.         laz[node][i]=0;
  61.     }
  62. }
  63. void getinfo(int node){
  64.     FOR(type,0,1){
  65.         mi[node][type]=(mi[node<<1][type].X<mi[node*2+1][type].X)?mi[node*2][type]:mi[node*2+1][type];
  66.         ma[node][type]=(ma[node<<1][type].X>ma[node*2+1][type].X)?ma[node*2][type]:ma[node*2+1][type];
  67.         sum[node][type]=(sum[node<<1][type]+sum[node*2+1][type]);
  68.     }
  69.     c[node]=c[node*2]+c[node*2+1];
  70.     S[node]=S[node*2]+S[node*2+1];
  71. }
  72. void update(int type,int node,int L,int R,int l,int r,int v){
  73.     lazyupdate(node,L,R);
  74.     if (L>r||R<l) return;
  75.     if (l<=L&&R<=r){
  76.         if (type>2) laz[node][type-3]+=v;
  77.         else h[node][type-1]=ii(v,1);
  78.         lazyupdate(node,L,R);
  79.         return;
  80.     }
  81.     update(type,node*2,L,(L+R)/2,l,r,v);
  82.     update(type,node*2+1,(L+R)/2+1,R,l,r,v);
  83.     getinfo(node);
  84. }
  85. ll query(int type,int node,int L,int R,int l,int r){
  86.     lazyupdate(node,L,R);
  87.     if (L>r||R<l) return 0;
  88.     if (l<=L&&R<=r) return (type?c[node]:S[node]);
  89.     return query(type,node*2,L,(L+R)/2,l,r)+query(type,node*2+1,(L+R)/2+1,R,l,r);
  90. }
  91. void clearnode(int node){
  92.     FOR(i,0,1){
  93.         mi[node][i].X=inf;
  94.         ma[node][i].X=-inf;
  95.         h[node][i]=ii(0,0);
  96.         laz[node][i]=0;
  97.         sum[node][i]=0;
  98.     }
  99.     c[node]=S[node]=0;
  100. }
  101. void erase(int node,int L,int R,int x){
  102.     lazyupdate(node,L,R);
  103.     if (L>x||R<x) return;
  104.     if (L==R){
  105.         clearnode(node);
  106.         return;
  107.     }
  108.     erase(node*2,L,(L+R)/2,x);
  109.     erase(node*2+1,(L+R)/2+1,R,x);
  110.     getinfo(node);
  111. }
  112. void build(int node,int L,int R){
  113.     if (L==R){
  114.         bool ok=!(a[L][0]>gold[0]||a[L][1]>gold[1]||a[L][0]<=0||a[L][1]<=0);
  115.         FOR(i,0,1){
  116.             mi[node][i]=ii(ok?a[L][i]:inf,L);
  117.             ma[node][i]=ii(ok?a[L][i]:-inf,L);
  118.             sum[node][i]=ok?a[L][i]:0;
  119.         }
  120.         c[node]=ok;
  121.         S[node]=ok?1LL*a[L][0]*a[L][1]:0;
  122.         return;
  123.     }
  124.     build(node*2,L,(L+R)/2);
  125.     build(node*2+1,(L+R)/2+1,R);
  126.     getinfo(node);
  127. }
  128. void detect(){
  129.     FOR(type,0,1){
  130.         while (ma[1][type].X>gold[type]){
  131.             int x=ma[1][type].Y;
  132.             erase(1,1,n,x);
  133.         }
  134.         while (mi[1][type].X<=0){
  135.             int x=mi[1][type].Y;
  136.             erase(1,1,n,x);
  137.         }
  138.     }
  139. }
  140. void check(int node,int L,int R){
  141.     printf("%d %d %d\n",node,L,R);
  142. //    printf("Max a:%d %d\n",ma[node][0].X,ma[node][0].Y);
  143. //    printf("Min a:%d %d\n",mi[node][0].X,mi[node][0].Y);
  144. //    printf("Max b:%d %d\n",ma[node][1].X,ma[node][1].Y);
  145. //    printf("Min b:%d %d\n",mi[node][1].X,mi[node][1].Y);
  146.     printf("%d %d\n",laz[node][0],laz[node][1]);
  147.     cout<<sum[node][0]<<" "<<sum[node][1]<<'\n'<<S[node]<<'\n';
  148.     if (L==R) return;
  149.     check(node*2,L,(L+R)/2);
  150.     check(node*2+1,(L+R)/2+1,R);
  151. }
  152. int main(){
  153. 	freopen("vmellip.inp", "r", stdin);
  154. 	freopen("vmellip.out", "w", stdout);
  155. //    INPUT;OUTPUT;
  156.     scanf("%d%d",&n,&m);
  157.     FOR(i,1,n)
  158.         FOR(j,0,1) scanf("%d",a[i]+j);
  159.     FOR(i,1,m) {
  160.         FOR(j,0,2) scanf("%d",q[i]+j);
  161.         if (q[i][0]<=4) scanf("%d",q[i]+3);
  162.     }
  163.     scanf("%d%d",gold,gold+1);
  164.     build(1,1,n);
  165. //    check(1,1,n);
  166.     FOR(i,1,m){
  167. //        printf("%d...\n",i);
  168.         if (q[i][0]<=4) update(q[i][0],1,1,n,q[i][1],q[i][2],q[i][3]);
  169.         else {
  170.             detect();
  171.             printf("%lld\n",query(q[i][0]-5,1,1,n,q[i][1],q[i][2]));
  172.         }
  173. //        check(1,1,n);
  174.     }
  175. }
Runtime error #stdin #stdout 0s 46696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jd2XXQ
language:
C++14 (gcc 8.3)
created:
8 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!