fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=300000+10;
  27. const int INF=2000000000;
  28.  
  29. int N,K;
  30. int sum[MAX],t[MAX];
  31.  
  32. void add(int a,int b)
  33. {
  34.     for(;a<MAX;a+=(a&(-a)))
  35.         sum[a]++;
  36. }
  37.  
  38. int ask(int a)
  39. {
  40.     int ans=0;
  41.     for(;a;a-=a&(-a))
  42.         ans+=sum[a];
  43.     return ans;
  44. }
  45.  
  46. pair<int,int> tree[MAX*4];
  47. int flag[MAX*4];
  48.  
  49. void flagit(int u,int d)
  50. {
  51.     flag[u]+=d;
  52.     tree[u].x+=d;
  53. }
  54.  
  55. void update(int u)
  56. {
  57.     tree[u]=max(tree[u*2],tree[u*2+1]);
  58. }
  59.  
  60. void down(int u)
  61. {
  62.     if(flag[u])
  63.     {
  64.         flagit(u*2,flag[u]);
  65.         flagit(u*2+1,flag[u]);
  66.         flag[u]=0;
  67.     }
  68. }
  69.  
  70. void build(int u,int l,int r)
  71. {
  72.     if(l==r)
  73.         tree[u]=mp(t[l]<0?t[l]:-INF,l);
  74.     else
  75.     {
  76.         int mid=(l+r)/2;
  77.         build(u*2,l,mid);
  78.         build(u*2+1,mid+1,r);
  79.         update(u);
  80.     }
  81. }
  82.  
  83. void add(int u,int l,int r,int a,int b,int x)
  84. {
  85.     if(r<a || b<l)
  86.         return;
  87.     if(a<=l && r<=b)
  88.         flagit(u,x);
  89.     else
  90.     {
  91.         down(u);
  92.         int mid=(l+r)/2;
  93.         add(u*2,l,mid,a,b,x);
  94.         add(u*2+1,mid+1,r,a,b,x);
  95.         update(u);
  96.     }
  97. }
  98.  
  99. pair<int,int> ask(int u,int l,int r,int a,int b)
  100. {
  101.     if(r<a || b<l)
  102.         return mp(-INF,0);
  103.     if(a<=l && r<=b)
  104.         return tree[u];
  105.     else
  106.     {
  107.         down(u);
  108.         int mid=(l+r)/2;
  109.         return max(ask(u*2,l,mid,a,b),ask(u*2+1,mid+1,r,a,b));
  110.     }
  111. }
  112.  
  113. void inicjuj(int n, int k, int *D)
  114. {
  115.     N=n;
  116.     K=k;
  117.     int i;
  118.     REP(i,1,n)
  119.     {
  120.         t[i]=D[i-1]-k;
  121.         if(t[i]>=0)
  122.             add(i,1);
  123.     }
  124.     build(1,1,n);
  125. }
  126.  
  127. void podlej(int a, int b)
  128. {
  129.     ++a;
  130.     ++b;
  131.     add(1,1,N,a,b,1);
  132.     pair<int,int> tmp;
  133.     while((tmp=ask(1,1,N,a,b)).x==0)
  134.     {
  135.         add(tmp.y,1);
  136.         add(1,1,N,tmp.y,tmp.y,-INF);
  137.     }
  138. }
  139.  
  140. int dojrzale(int a, int b)
  141. {
  142.     ++a;
  143.     ++b;
  144.     return ask(b)-ask(a-1);
  145. }
  146.  
  147. int main()
  148. {
  149.     return 0;
  150. }
  151.  
Success #stdin #stdout 0s 19696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QRb87C
language:
C++ (gcc 8.3)
created:
10 years 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!