fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define f(i,n) for(i=0;i<n;i++)
  4. #define pb push_back
  5. #define mod 1000000007
  6. #define mp make_pair
  7. #define ff first
  8. #define ss second
  9. #define ll int
  10. #define ld long double
  11. #define gc getchar
  12. #define pc putchar
  13. #define sort1(a) sort(a.begin(),a.end())
  14. #define sort2(a,n) sort(a,a+n)
  15. #define vvl vector <vector <ll> >
  16. #define vl vector <ll>
  17. inline ll uscan()
  18. {
  19.     ll n=0,c=gc();
  20.     bool check=0;
  21.     if(c=='-')check=1;
  22.     while(c<'0'||c>'9')
  23.     {
  24.         c=gc();
  25.         if(c=='-')check=1;
  26.     }
  27.     while(c<='9'&&c>='0'){
  28.         n=n*10+c-'0';
  29.         c=gc();
  30.     }
  31.     return n+(-2*check*n);
  32. }
  33. #define sc uscan()
  34. void prin(vector <ll> a){
  35.     ll i;
  36.     f(i,a.size()){
  37.         cout<<a[i]<<' ';
  38.     }pc('\n');
  39. }
  40. void prin(vector <vector <ll> > a){
  41.     ll i,j;
  42.     f(i,a.size()){
  43.         f(j,a[i].size())
  44.             cout<<a[i][j]<<' ';
  45.         pc('\n');
  46.     }
  47.     pc('\n');
  48. }
  49.  
  50. #define MAXNUM 200000
  51.  
  52. // #define block_size 1
  53.  
  54. #ifndef block_size
  55.     #define block_size 400
  56. #endif
  57.  
  58. const ll number_of_blocks_half=ceil((ld)MAXNUM/(ld)block_size);
  59. const ll number_of_blocks=number_of_blocks_half<<1;
  60.  
  61. #define thisproblemisapain(a,b,c,d,e) mp(a,mp(mp(b,c),mp(d,e)))
  62. #define pllllll pair <ll,pair <pair <ll,ll> ,pair <ll,ll> > >
  63. int main()
  64. {
  65.     ll q=sc,k=sc;
  66.  
  67.     ll ans=0;
  68.     vector <pllllll > maxans[number_of_blocks];
  69.     pair <ll,ll> a[number_of_blocks*block_size]={mp(-1,0)};
  70.     ll l=number_of_blocks_half*block_size;
  71.     ll r=l-1;
  72.  
  73.     while(q--){
  74.            // if(q==5e4)break;
  75.         ll b=sc,C=sc;
  76.         ll c=C^ans;
  77.         if(b!=3){
  78.             ll d=sc;
  79.             ll block_num=-1;
  80.             if(b==1){
  81.                 l--;
  82.                 a[l].ss=d;
  83.                 a[l].ff=c;                
  84.                 if(((l+1)%block_size)==0&&l+1!=number_of_blocks_half*block_size){
  85.                     block_num=(l+1)/block_size;
  86.                 }
  87.             }
  88.             else{
  89.                 r++;
  90.                 a[r].ss=d;
  91.                 a[r].ff=c;
  92.                 if(r%block_size==0&&r!=number_of_blocks_half*block_size){
  93.                     block_num=(r-1)/block_size;
  94.                 }
  95.             }
  96.             if(block_num!=-1){
  97.                 // O(block_size^2 + block_size*log(block_size))
  98.                 ll star=block_num*block_size;
  99.                 ll en=star+block_size-1;
  100.                 ll maxim=0,minim=INT_MAX;
  101.                 for(ll ii=0;ii<(block_size*2);ii++){
  102.  
  103.                     maxim=max(maxim,a[star+(ii/2)].ff);
  104.                     minim=min(minim,a[star+(ii/2)].ff);
  105.  
  106.                     ll valid_c=a[star+ii/2].ff-k;
  107.                     if(ii%2)
  108.                         valid_c+=(k<<1)+1;
  109.                     // if(ii%3==2){
  110.                     //     valid_c++;
  111.                     // }
  112.                     ll MA=0,ML=0,MR=0;
  113.                     ll ml=0,mr=0,bs=0,ma=0;
  114.                     for(ll i=star;i<=en;i++){
  115.                         if(a[i].ff<=valid_c+k&&a[i].ff>=valid_c-k){
  116.                             bs+=a[i].ss;
  117.                             if(i-star){
  118.                                 MA=a[i].ss+max(MA,0);
  119.                                 ML=ML+a[i].ss;
  120.                             }
  121.                             else{
  122.                                 MA=max(0,a[i].ss);
  123.                                 ML=a[i].ss;
  124.                             }
  125.                         }
  126.                         ma=max(ma,MA);
  127.                         ml=max(ml,ML);
  128.                         mr=min(mr,ML);
  129.                     }
  130.                     mr=bs-mr;
  131.                     mr=max(mr,bs);
  132.                     maxans[block_num].pb(thisproblemisapain(valid_c,ml,mr,bs,ma));
  133.                 }
  134.                 maxans[block_num].pb(thisproblemisapain(maxim+1+k,0,0,0,0));
  135.                 maxans[block_num].pb(thisproblemisapain(minim-1-k,0,0,0,0));
  136.                 maxans[block_num].pb(thisproblemisapain(INT_MAX,0,0,0,0));
  137.                 maxans[block_num].pb(thisproblemisapain(-INT_MAX,0,0,0,0));
  138.                 sort1(maxans[block_num]);
  139.             }
  140.         }
  141.         else{
  142.             // query
  143.             ans=0;
  144.             ll dp=0;
  145.             ll cur_block=l/block_size;
  146.             ll start_block=cur_block;
  147.             ll last_block=r/block_size;
  148.  
  149.             // fill dp[curblock]
  150.             ll MA1=0,ML1=0;
  151.             ll mr1=0,bs1=0;
  152.             ll star1=l,en1=block_size*(cur_block+1)-1;
  153.             // cout<<star1<<' '<<en1<<'\n';
  154.             for(ll i=star1;i<=en1;i++){
  155.                 if(a[i].ff<=c+k&&a[i].ff>=c-k){
  156.                     bs1+=a[i].ss;
  157.                     if(i-star1){
  158.                         MA1=a[i].ss+max(MA1,0);
  159.                         ML1=ML1+a[i].ss;
  160.                     }
  161.                     else{
  162.                         MA1=max(0,a[i].ss);
  163.                         ML1=a[i].ss;
  164.                     }
  165.                     ans=max(ans,MA1);
  166.                     mr1=min(mr1,ML1);
  167.                 }
  168.             }
  169.             mr1=bs1-mr1;
  170.             mr1=max(mr1,bs1);
  171.             dp=mr1;
  172.             pllllll search_dummy=thisproblemisapain(c,-1,-1,-1,-1);
  173.             for(cur_block++;cur_block<last_block;cur_block++){
  174.                 ll bs=-INT_MAX,mr=0,ml=0;
  175.                 // search <=c
  176.  
  177.                 ll tem=lower_bound(maxans[cur_block].begin(),maxans[cur_block].end(),search_dummy)-maxans[cur_block].begin();
  178.                 if(tem==(ll)maxans[cur_block].size()){
  179.                     tem--;
  180.                 }                
  181.                 if(maxans[cur_block][tem].ff>c&&tem){
  182.                     tem--;
  183.                 }
  184.                 ans=max(maxans[cur_block][tem].ss.ss.ss,ans);
  185.                 bs=maxans[cur_block][tem].ss.ss.ff;
  186.                 mr=max(mr,maxans[cur_block][tem].ss.ff.ss);
  187.                 ml=max(ml,maxans[cur_block][tem].ss.ff.ff);
  188.  
  189.                 ans=max(ans,ml+dp);
  190.                 dp=max(bs+dp,mr);
  191.             }
  192.  
  193.             ll MA2=0,ML2=0;
  194.             ll ml2=0;
  195.             ll star2=last_block*block_size,en2=r;
  196.             for(ll i=star2;i<=en2;i++){
  197.                 if(a[i].ff<=c+k&&a[i].ff>=c-k){
  198.                     if(i-star2){
  199.                         MA2=a[i].ss+max(MA2,0);
  200.                         ML2=ML2+a[i].ss;
  201.                     }
  202.                     else{
  203.                         MA2=max(0,a[i].ss);
  204.                         ML2=a[i].ss;
  205.                     }
  206.                     ml2=max(ml2,ML2);
  207.                     ans=max(ans,MA2);
  208.                 }
  209.             }
  210.             if(last_block-1>=start_block)
  211.                 ans=max(ans,dp+ml2);
  212.             cout<<ans<<'\n';
  213.         }
  214.     }
  215.  
  216.  
  217. 	return 0;
  218. }
Time limit exceeded #stdin #stdout 5s 18264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/74ASpH
language:
C++14 (gcc 8.3)
created:
5 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!