fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long int ll;
  6.  
  7. #define mp make_pair
  8. #define pb push_back
  9. #define pii pair<int, int>
  10.  
  11. map<ll, ll> lft, rgt;
  12. map<ll, ll> val;
  13.  
  14. ll qry(ll l, ll r){
  15.     if(val.find(r) == val.end()) return r;
  16.     auto it = rgt.upper_bound(r);
  17.     if(rgt.find(r) != rgt.end()) it = rgt.find(r);
  18.     if(it -> second <= l) return 0;
  19.     return (it -> second - 1);
  20. }
  21.  
  22. void clear(){
  23.     val.clear();
  24.     lft.clear();
  25.     rgt.clear();
  26. }
  27.  
  28. void update(int x){
  29.     if(val.find(x) != val.end()) return;
  30.     val[x] = 0;
  31.     if(rgt.find(x-1) != rgt.end()){
  32.         ll l = rgt[x-1];
  33.         rgt.erase(rgt.find(x-1));
  34.         rgt[x] = l;
  35.     }else{
  36.         rgt[x] = x;
  37.     }
  38.     auto it = rgt.upper_bound(x);
  39.     if(it != rgt.end()){
  40.         ll l = it -> second;
  41.         if(l == x+1){
  42.             ll r = it -> first;
  43.             ll _l = rgt[x];
  44.             rgt.erase(rgt.find(x));
  45.             rgt[r] = _l;
  46.         }
  47.     }
  48. }
  49.  
  50. void print(){
  51.     for(auto i :rgt ) cout << "(" << i.first << " " << i.second << ") "; cout << endl;
  52. }
  53.  
  54. int main(){
  55.     ios_base :: sync_with_stdio(0);
  56.     cin.tie(0);
  57.  
  58.     int t;
  59.     cin >> t;
  60.     while(t--){
  61.         clear();
  62.         ll n, q, s = 0;
  63.         cin >> n >> q;
  64.         while(q--){
  65.             int ty;
  66.             cin >> ty;
  67.             if(ty == 1){
  68.                 ll x;
  69.                 cin >> x;
  70.                 //x += s;
  71.                 update(x);
  72.                 //cout << x << endl;
  73.             }else{
  74.                 ll l, r;
  75.                 cin >> l >> r;
  76.                 //l += s, r += s;
  77.                 ll ans = qry(l, r);
  78.                 s = (s  + ans) % n;
  79.                 cout << ans << '\n';
  80.             }
  81.            // print();
  82.         }
  83.     }
  84.     return 0;
  85. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1
10 10
1 3
1 5
1 7
1 9
1 2
1 6
1 8
2 2 5
2 1 10
2 4 9
stdout
copy 
4
10
4
https://ideone.com/58RP2N
language:
C++14 (gcc 8.3)
created:
4 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!