fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define all(a,x) a.begin()+x, a.end()
  5. #define pii pair<int, int>
  6. using ll = long long;
  7. const long long INF = 1e18;
  8. const int inf = 1e9;
  9. void read(){
  10.    #define TASK "DULIEU"
  11.       if(fopen(TASK ".INP", "r")){
  12.          freopen(TASK ".INP", "r", stdin);
  13.          //freopen(TASK ".OUT", "w", stdout);
  14.       }
  15. }
  16. int n, q;
  17. vector<int> st;
  18. void update(int id, int l, int r, int pos, int val){
  19.     if(l == r){
  20.         st[id] = val;
  21.         return;
  22.     }
  23.     int m = (l+r)/2;
  24.     if(pos <= m) update(2*id, l, m, pos, val);
  25.     else update(2*id+1, m+1, r, pos, val);
  26.     st[id] = max(st[2*id], st[2*id+1]);
  27. }
  28. int walk(int id, int l, int r, int u, int v, int val){
  29.     if(u > r || v < l || st[id] <= val) return -1;
  30.     if(l == r) return l;
  31.     int m = (l+r)/2;
  32.     int res = walk(2*id+1, m+1, r, u, v, val);
  33.     if(res != -1) return res;
  34.     return walk(2*id, l, m, u, v, val);
  35. }
  36. void solve(){
  37.     cin >> n >> q;
  38.     vector<multiset<int>> s(n+2);
  39.     st.assign(4*n+1, -inf);
  40.     while(q--){
  41.         int type; cin >> type;
  42.         if(type == 1){
  43.             int pos, val; cin >> pos >> val;
  44.             s[pos].insert(val);
  45.             int cur = *s[pos].rbegin();
  46.             update(1,1,n,pos,cur);
  47.         }
  48.         else if(type == 2){
  49.             int pos, val; cin>> pos >> val;
  50.             auto it = s[pos].find(val);
  51.             if(it != s[pos].end()){
  52.                 s[pos].erase(it);
  53.                 int cur = s[pos].empty() ? -inf : *s[pos].rbegin();
  54.                 update(1,1,n,pos,cur);
  55.             }
  56.         }
  57.         else{
  58.             int l, r, val; cin >> l >> r >> val;
  59.             int ans = walk(1,1,n,l,r,val);
  60.             if(ans == -1) cout << "NONE" << '\n';
  61.             else cout << ans << '\n';
  62.         }
  63.     }
  64. }
  65. signed main(){
  66.     ios::sync_with_stdio(false);cin.tie(nullptr);
  67.     read();
  68.     int t=1; //cin >> t;
  69.     while(t--) solve();
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tuShXP
language:
C++14 (gcc 8.3)
created:
2 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!