fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int,int> PII;
  5.  
  6. const int MAXN=2e5+5;
  7. const int LOG=19;
  8. const int BASE=1<<LOG;
  9.  
  10. int tree1[2*BASE+5];
  11. int tree2[2*BASE+5];
  12. int n;
  13. long long N1,H1,N2,H2;
  14. long long x[MAXN];
  15. long long h[MAXN];
  16.  
  17. vector<pair<int,int>>used;
  18.  
  19. struct Group
  20. {
  21.     int count;
  22.   long long start;
  23.   long long end;
  24.  
  25. };
  26.  
  27. PII query1 (long long n)
  28. {
  29.     int idx=1;
  30.     int sum=0;
  31.     while(idx<BASE)
  32.     {
  33.         if(tree1[idx*2+1]+sum>n)
  34.         {
  35.             idx=idx*2+1;
  36.         }
  37.         else
  38.         {
  39.             idx=idx*2;
  40.             sum+=tree1[idx+1];
  41.         }
  42.     }
  43.     return {idx-BASE,sum};
  44. }
  45. long long query2(int l, int r)
  46. {
  47.     l+=BASE-1;
  48.     r+=BASE+1;
  49.     long long res=0;
  50.     while(l/2!=r/2)
  51.     {
  52.         if(l%2==0)
  53.         {
  54.             res+=tree2[l+1];
  55.         }
  56.         if(r%2==1)
  57.         {
  58.             res+=tree2[r-1];
  59.         }
  60.         l/=2;
  61.         r/=2;
  62.     }
  63.     return res;
  64. }
  65. void update(int idx, int val)
  66. {
  67.     if (idx == 0) return;
  68.  
  69.     int add = val * ((idx+H2-1) / H2);
  70.     idx+=BASE;
  71.     tree1[idx]+=val;
  72.     tree2[idx]+=add;
  73.     idx/=2;
  74.     while(idx)
  75.     {
  76.         tree1[idx]=tree1[idx*2]+tree1[idx*2+1];
  77.         tree2[idx]=tree2[idx*2]+tree2[idx*2+1];
  78.         idx/=2;
  79.     }
  80.  
  81. }
  82. bool check (long long n1, long long n2)
  83. {
  84.     PII q1=query1(n1);
  85.     int atidx=tree1[q1.first+BASE];
  86.     n1-=q1.second;
  87.     atidx-=n1;
  88.     int needed = atidx * ((q1.first+H2-1)/H2);   // overflow
  89.  
  90.     // czasami nie trzeba robic query?
  91.     long long q2=query2(0, q1.first-1);
  92.  
  93.     /*if(n2>=q2+needed)
  94.     {
  95.         return true;
  96.     }
  97.     return false;*/
  98.  
  99.     return n2 >= q2+needed;
  100. }
  101. vector<Group>Groups;
  102. int main()
  103. {
  104.     cin>>n;
  105.     for(int i=0; i<n; i++)
  106.     {
  107.         cin>>x[i]>>h[i];
  108.     }
  109.     cin>>N1>>H1>>N2>>H2;
  110.     if(H2>H1)
  111.     {
  112.         swap(H1,H2);
  113.         swap(N1,N2);
  114.     }
  115.     int l=0;
  116.     int r=0;
  117.     long long end;
  118.     while(l<n)
  119.     {
  120.         end=x[l]+h[l];
  121.         r=l+1;
  122.         while(r<n and end>=x[r])
  123.         {
  124.             end=max(end, x[r]+h[r]);
  125.             r++;
  126.         }
  127.         Groups.push_back({r-l, x[l], end});
  128.         l=r;
  129.     }
  130.     used.resize(Groups.size(), {0LL, 0LL});
  131.     r=1;
  132.     long long n1=N1;
  133.     long long n2=N2;
  134.     long long h1=H1;
  135.     long long h2=H2;
  136.     long long cur=Groups[0].count;
  137.     long long res=cur;
  138.     for(int l=0; l<Groups.size(); l++)
  139.     {
  140.         n1+=used[l].first;
  141.         n2+=used[l].second;
  142.         while(check(n1,n2))
  143.         {
  144.             cur+=Groups[r].count;
  145.             res=max(res,cur);
  146.             long long len=Groups[r].start-Groups[r-1].end;
  147.             long long takeLow=0;
  148.             long long takeHigh=len/H1;
  149.             if(takeHigh>n1)
  150.             {
  151.                 takeLow=(takeHigh-n1)*(H1/H2);
  152.                 if(takeLow>n2)
  153.                 {
  154.                     break;
  155.                 }
  156.                 takeHigh=n1;
  157.                 n1=0;
  158.                 n2-=takeLow;
  159.             } else {
  160.                 n1 -= takeHigh;
  161.             }
  162.             used[r]={takeHigh, takeLow};
  163.             len %= H1;
  164.             update(len, 1);
  165.  
  166.             r++;
  167.  
  168.         }
  169.         cur-=Groups[l].count;
  170.         update((Groups[l+1].start-Groups[l].end) % H1, -1);
  171.  
  172.     }
  173.     cout << res + N1 + N2;
  174.     return 0;
  175. }
  176.  
Success #stdin #stdout 0s 9764KB
comments (?)
stdin
copy 
3
1 5
10 6
20 7
1 4 2 1
stdout
copy 
6
https://ideone.com/sYZ1d4
language:
C++14 (gcc 8.3)
created:
237 days 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!