fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define db long double
  4. #define pll pair<ll,ll>
  5. #define foru(i,a,b) for(ll i=(a);i<=(b);i++)
  6. #define ford(i,a,b) for(ll i=(a);i>=(b);i--)
  7. #define ALL(a) (a).begin(),(a).end()
  8. #define ROUND(i) fixed<<setprecision(i)
  9. #define fi first
  10. #define se second
  11. using namespace std;
  12. clock_t start_time=clock();
  13. int NumTest=1,CurTest;
  14. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  15. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣶⣾⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  16. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⡞⠀⠀⢀⣤⣴⣾⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀⣀⠀⠀⠀⠀⠀⠀⠀
  17. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣶⣿⣿⣣⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣤⣶⣾⣿⠃⠀⠀⠀⠀⠀⠀⠀
  18. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⣀⣀⣀⡤⠀⠀⠀
  19. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀
  20. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀
  21. ///⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀
  22. ///⠀⠀⠀⠀⠀⠀⠀⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣤⣶⣾⡟⠀
  23. ///⠀⠀⠀⠀⠀⠀⡰⢹⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⠀
  24. ///⠀⠀⠀⠀⠀⢠⣳⣿⣾⣿⣿⣿⣿⢋⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀
  25. ///⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣿⣿⣿⡞⠀⠈⠙⠿⠿⠟⠛⠉⠀⠀⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠀⠀⠀
  26. ///⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⠁⠀⠀⡄⠀⠀⠀⠀⠀⠀⠐⡄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⠀⠀⠀
  27. ///⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⢿⣿⣿⠀⠀⡌ -TFA-⠀⠀ ⠀⢻⣿⣿⡇⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣴⡶⠋⠁
  28. ///⠀⠀⠀⠀⢸⣿⣿⣿⣿⡟⢻⣿⣧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣼⣿⣿⠗⢺⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠀⠀⠀
  29. ///⠀⠀⠀⠀⢸⣿⣿⣿⣿⣇⣀⣻⣇⠈⣖⣄⠀⠀⠀⢀⡤⠖⣻⢍⣁⣀⣿⣏⡀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠋⠀⠀⠀⠀
  30. ///⠀⠀⠀⠀⢸⡿⣿⣿⣿⡇⢻⢻⣿⣿⣶⡽⠂⠀⠀⠀⠀⢽⣵⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣵⣶⠖⠋⠀⠀
  31. ///⠀⠀⠀⠀⢸⡇⢸⣿⣿⣿⡈⠘⢛⣿⢿⡇⠀⠀⠀⠀⠀⠈⠡⠼⠏⣻⣿⡿⢻⠏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠁⠀⠀⠀⠀
  32. ///⠀⠀⠀⠀⢸⠁⠈⣿⣿⣿⡇⠈⠪⠷⠚⠁⠀⠀⠀⠀⠀⠀⠀⠀⠈⠽⠷⠞⠃⠀⢸⣿⣿⣿⣿⢏⣿⣿⣿⡟⠁⠀⠀⠀⠀⠀⠀
  33. ///⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⣷⠀⠀⠀⠀⠀⠀⢀⢠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⢸⣿⣿⣿⣏⣡⣿⣿⣿⣇⠀⠀⠀⠀⠀⠀⠀
  34. ///⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣧⡀⠀⠀⠀⠀⠀⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⠃⢸⣿⣿⣿⣿⣿⡟⠀⠉⠛⠣⠀⠀⠀⠀⠀⠀
  35. ///⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⡟⠙⠢⣄⠀⠀⠀⠒⢂⠠⠀⠀⠀⠀⠀⠀⢈⡠⠔⢻⣿⣿⡟⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  36. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⡿⠇⠀⠀⡨⠋⢲⠤⣀⠈⠀⢀⣀⡀⠤⢖⠞⠉⠀⠀⢸⡟⠻⣄⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  37. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡇⠀⡠⠊⠐⡄⠀⠀⡀⠉⠉⠉⠀⠀⢀⠎⠀⠀⠀⠀⠟⠀⠀⠈⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  38. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡁⠀⠀⠁⣆⠏⠈⢓⠒⠋⠁⣄⠞⠀⠀⠀⠀⠀⠀⠐⢈⡤⠒⠛⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  39. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⡻⣠⠀⠀⠀⡿⠀⠀⠀⠀⠀⠀⡜⠀⠀⠀⠀⠀⠀⠀⡴⠋⠀⠳⡀⠸⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  40. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⡜⠁⠀⡟⠀⠀⠀⡇⠀⠀⠀⠀⠀⢰⠁⠀⠀⠀⠀⠀⢀⠜⠀⠀⠀⠀⠀⠀⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀
  41. ///⠀⠀⠀⠀⠀⠀⣀⠠⠞⠀⠀⢀⠇⠀⠀⠀⡇⠀⠀⠀⠀⢀⡆⠀⠀⠀⠀⠀⠀⡌⠀⢀⠂⠀⠀⠀⠀⠈⡄⠀⠀⠀⠀⠀⠀⠀⠀
  42. ///⠀⠀⠀⣠⠔⠊⠁⠀⠀⠀⠀⢸⠀⠀⠀⠀⡇⠀⠀⠀⠀⡜⠀⠀⠀⠀⠀⠀⠀⡇⠀⡜⠀⠀⠀⠀⠀⠀⢹⡀⠀⠀⠀⠀⠀⠀⠀
  43. ///⣠⣖⠉⠁⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀⠀⠀⢰⣀⡀⠀⡼⠀⠀⠀⠒⠀⠀⠠⠂⠇⢠⠁⠀⠀⠀⠀⠀⠀⠀⢇⠀⠀⠀⠀⠀⠀⠀
  44. ///⠸⣟⣿⡇⠀⠀⠀⠀⠀⠀⢠⣷⣖⡒⣆⠀⢲⣷⣉⠞⣠⠖⠒⠒⠲⢤⣤⣀⣀⣰⡜⠀⠀⠀⠀⠀⠀⠀⠀⠸⡄⠀⠀⠀⠀⠀⠀
  45. ///⠀⠀⠈⢹⡀⠀⠀⠀⠀⠀⠀⢹⣽⣒⣼⣿⣿⣿⣧⡞⠓⠒⠀⢀⣴⣯⣾⣷⡘⢻⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⢣⠀⠀⠀
  46. const ll N=3e5+5;
  47. const ll INF=1e15;
  48. ll n,q;
  49.  
  50.  
  51. ll value[4*N];
  52. bool havlz[4*N];
  53. ll lzs[4*N], lzv[4*N];
  54.  
  55. void push(ll id,ll il,ll ir,ll s,ll v){
  56.     value[id]=max(il*s+v, ir*s+v);
  57.     lzs[id]=s; lzv[id]=v;
  58.     havlz[id]=1;
  59. }
  60. void down(ll id,ll il,ll ir){
  61.     if(!havlz[id]) return;
  62.     ll im=(il+ir)>>1;
  63.     push(id*2,il,im,lzs[id],lzv[id]);
  64.     push(id*2+1,im+1,ir,lzs[id],lzv[id]);
  65.     havlz[id]=0;
  66. }
  67. void Update(ll id,ll il,ll ir,ll l,ll r,ll s,ll v){
  68.     if(il>r||ir<l) return;
  69.     if(l<=il&&ir<=r){   
  70.         push(id,il,ir,s,v);
  71.         return;     
  72.     }
  73.     ll im=(il+ir)>>1;
  74.     down(id,il,ir);
  75.     Update(id*2,il,im,l,r,s,v);
  76.     Update(id*2+1,im+1,ir,l,r,s,v);
  77.     value[id]=max(value[id*2], value[id*2+1]);
  78. }
  79. ll Get(ll id,ll il,ll ir,ll l,ll r){
  80.     if(il>r||ir<l) return 0;
  81.     if(l<=il&&ir<=r) return value[id];
  82.     down(id,il,ir);
  83.     ll im=(il+ir)>>1;
  84.     return max(Get(id*2,il,im,l,r),Get(id*2+1,im+1,ir,l,r));
  85. }
  86.  
  87. set<ll>SL={-INF,+INF};
  88. set<ll>SR={-INF,+INF};
  89.  
  90. void Uchiha_Sasuke(){
  91.     cin>>n>>q;
  92.  
  93.     memset(value,0x3f,sizeof(value));
  94.  
  95.     foru(turn,1,q){
  96.         int type; cin>>type;
  97.         if(type==1){
  98.             ll dir,start; cin>>dir>>start;
  99.             if(dir==0){ 
  100.                 SL.insert(start);
  101.                 ll Lim=max(1ll,*(--SL.lower_bound(start))+1);
  102.                 ll cur=start;
  103.                 while(cur>=Lim){
  104.                     auto it=--SR.upper_bound(cur-(start-cur+1)+1);
  105.                     // cerr<<start<<' '<<cur<<' '<<cur-(start-cur+1)*2+1<<'\n';
  106.                     ll L=*it;
  107.                     ll l=start-(start-L+1)/2+1; l=max(l,Lim);
  108.                     ll r=min(cur,*next(it)-1);
  109.                     Update(1,1,n,l,r,-1,+start);
  110.                     cur=L-1;
  111.                 }   
  112.             }
  113.             else{
  114.                 SR.insert(start);
  115.                 ll Lim=min(n,*SR.upper_bound(start)-1);
  116.                 ll cur=start;
  117.                 while(cur<=Lim){
  118.                     auto it=SL.lower_bound(cur+(cur-start+1)-1);
  119.                     ll R=*it;
  120.                     ll l=max(cur,*prev(it)+1);
  121.                     ll r=start+(R-start+1)/2-1; r=min(r,Lim);
  122.                     Update(1,1,n,l,r,+1,-start);
  123.                     cur=R+1;
  124.                 } 
  125.             }
  126.             // foru(i,1,n){
  127.             //     ll d=Get(1,1,n,i,i);
  128.             //     if(d>INF)cout<<"oo ";
  129.             //     else cout<<d<<' ';
  130.             // }
  131.             // cout<<'\n';
  132.         }
  133.         else{
  134.             ll l,r; cin>>l>>r;
  135.             ll res=Get(1,1,n,l,r);
  136.             cout<<((res<INF)?res:-1)<<'\n';
  137.         }                    
  138.     }
  139. }   
  140.  
  141. signed main(){
  142.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  143.     if(fopen("task.inp","r"))
  144.     freopen("task.inp","r",stdin),
  145.     freopen("task.out","w",stdout);
  146.     srand(time(0));
  147.  
  148.     //cin>>NumTest;
  149.     for(CurTest=1;CurTest<=NumTest;CurTest++)Uchiha_Sasuke();
  150.  
  151.     clock_t finish_time=clock();
  152.     double runtime=((double)finish_time-(double)start_time)/CLOCKS_PER_SEC;
  153.     cerr<<"\n---------------------------------------\nRun time : "<<fixed<<setprecision(4)<<(double)runtime<<'\n';
  154.     return 0;
  155. }
  156.  
Success #stdin #stdout #stderr 0.01s 13172KB
comments (?)
stdin
copy 
1
2
10
42
11
stdout
copy 
0
0
stderr
copy 
---------------------------------------
Run time : 0.0042
https://ideone.com/aMHVXb
language:
C++ (gcc 8.3)
created:
1 day 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!