fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define maxx 100005
  5. #define base 36
  6. #define MOD 1003472009
  7. #define x first
  8. #define y second
  9. long long n, a[maxx], pre[maxx], s[maxx], dp[maxx], l, r, vt[maxx];
  10. pair<long long, long long> p[maxx];
  11. void update(int id, int x, int y, int u, long long v)
  12. {
  13.     if(x>u||y<u) return;
  14.     if(x==y&&x==u)
  15.     {
  16.         s[id]=v;
  17.         return;
  18.     }
  19.     int mid=(x+y)/2;
  20.     update(id*2, x, mid, u, v);
  21.     update(id*2+1, mid+1, y, u, v);
  22.     s[id]=max(s[id*2], s[id*2+1]);
  23. }
  24. long long get(int id, int x, int y, int u, int v)
  25. {
  26.     if(x>v||y<u) return -1e18;
  27.     if(x>=u&&y<=v) return s[id];
  28.     int mid=(x+y)/2;
  29.     return max(get(id*2, x, mid, u, v), get(id*2+1, mid+1, y, u, v));
  30. }
  31. int main()
  32. {
  33.     ios_base::sync_with_stdio(0);
  34.     cin.tie(0); cout.tie(0);
  35.     memset(s, -61, sizeof(s));
  36.     cin>>n>>l>>r;
  37.     for(int i=1; i<=n; i++)
  38.     {
  39.         int x, y;
  40.         cin>>x>>y;
  41.         a[i]=x-y;
  42.         pre[i]=pre[i-1]+a[i];
  43.         p[i]={pre[i], i};
  44.     }
  45.     sort(p, p+n+1);
  46.     for(int i=0; i<=n; i++)
  47.     {
  48.         vt[p[i].y]=i;
  49.         //cout<<p[i].x<<" "<<p[i].y<<"\n";
  50.     }
  51.     for(int i=1; i<=n; i++)
  52.     {
  53.         dp[i]=-1e18;
  54.         if(i-l>=0) update(1, 0, n, vt[i-l], dp[i-l]);
  55.         if(i-r-1>=0) update(1, 0, n, vt[i-r-1], -1e18);
  56.         int x=0, y=n, u=vt[i], v=vt[i];
  57.         while(x<=y)
  58.         {
  59.             int mid=(x+y)/2;
  60.             if(p[mid].x<=p[vt[i]].x) v=mid, x=mid+1;
  61.             else y=mid-1;
  62.         }
  63.         x=0, y=n;
  64.         while(x<=y)
  65.         {
  66.             int mid=(x+y)/2;
  67.             if(p[mid].x>=p[vt[i]].x) u=mid, y=mid-1;
  68.             else x=mid+1;
  69.         }
  70.         //cout<<u<<" "<<v<<"\n";
  71.         dp[i]=max({get(1, 0, n, u, v), get(1, 0, n, 0, u-1)+1, get(1, 0, n, v+1, n)-1});
  72.         //cout<<dp[i]<<" ";
  73.     }
  74.     cout<<dp[n];
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0.01s 7588KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xp0qI6
language:
C++14 (gcc 8.3)
created:
3 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!