fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define cint const int
  4. #define pb push_back
  5. #define mid(l, r) ((l + r) >> 1)
  6. #define left(id) (id << 1)
  7. #define right(id) (id << 1 | 1)
  8.  
  9. const int MAXN = 2e5 + 15;
  10. const int oo   = 1e9;
  11.  
  12. int N, Q;
  13. int A[MAXN];
  14.  
  15. struct query {
  16.     int t, x, a, b;
  17. } q[MAXN];
  18.  
  19. struct ZIP {
  20.     vector<int> v;
  21.  
  22.     void ADD(int x) {
  23.         v.pb(x);
  24.     }
  25.  
  26.     void INIT() {
  27.         sort(v.begin(), v.end());
  28.         v.resize(distance(v.begin(), unique(v.begin(), v.end())));
  29.     }
  30.  
  31.     int get(int x) {
  32.         return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
  33.     }
  34. } ZIP;
  35.  
  36. struct Seg {
  37.     struct DATA {
  38.         int ma = -oo;
  39.         int L = -oo;
  40.         int R = -oo;
  41.         int S = -oo;
  42.     } it[MAXN * 9];
  43.  
  44.     DATA Merge(DATA a, DATA b) {
  45.         DATA ans;
  46.         ans.S = a.S + b.S;
  47.         if (ans.S < -oo) ans.S = -oo;
  48.         ans.L = max(a.L, a.S + b.L);
  49.         ans.R = max(b.R, a.R + b.S);
  50.         ans.ma = max({a.ma, b.ma, a.R + b.L});
  51.         return ans;
  52.     }
  53.  
  54.     void update(cint &id, cint &l, cint &r, cint &u, cint &v, cint &t) {
  55.         if (l > v || r < u) return;
  56.         if (u <= l && r <= v) {
  57.             if (t == 1) it[id].S = it[id].L = it[id].R = it[id].ma = 1;
  58.             else it[id].L = it[id].R = it[id].S = it[id].ma = -oo;
  59.             return;
  60.         }
  61.  
  62.         int mid = mid(l, r);
  63.         update(left(id), l, mid, u, v, t);
  64.         update(right(id), mid + 1, r, u, v, t);
  65.  
  66.         it[id] = Merge(it[left(id)], it[right(id)]);
  67.     }
  68.  
  69.     DATA get(cint &id, cint &l, cint &r, cint &u, cint &v) {
  70.         if (l > v || r < u) return {-oo, -oo, -oo, -oo};
  71.         if (u <= l && r <= v) return it[id];
  72.  
  73.         int mid = mid(l, r);
  74.         DATA it1 = get(left(id), l, mid, u, v);
  75.         DATA it2 = get(right(id), mid + 1, r, u, v);
  76.  
  77.         return Merge(it1, it2);
  78.     }
  79. } ST;
  80.  
  81.  
  82. signed main() {
  83.     ios_base::sync_with_stdio(0);
  84.     cin.tie(0);
  85.     cout.tie(0);
  86.  
  87.  
  88.     cin >> N >> Q;
  89.     map<int, int> m;
  90.     for (int i = 1; i <= N; i++) {
  91.         cin >> A[i];
  92.         m[A[i]]++;
  93.         ZIP.ADD(A[i]);
  94.         ZIP.ADD(A[i] + 1);
  95.         ZIP.ADD(A[i] - 1);
  96.     }
  97.  
  98.     for (int i = 1; i <= Q; i++) {
  99.         char c;
  100.         cin >> c;
  101.         if (c == '-') {
  102.             q[i].t = 1;
  103.             cin >> q[i].x;
  104.             ZIP.ADD(q[i].x);
  105.             ZIP.ADD(q[i].x + 1);
  106.             ZIP.ADD(q[i].x - 1);
  107.         }
  108.         if (c == '+') {
  109.             q[i].t = 2;
  110.             cin >> q[i].x;
  111.             ZIP.ADD(q[i].x);
  112.             ZIP.ADD(q[i].x + 1);
  113.             ZIP.ADD(q[i].x - 1);
  114.         }
  115.         if (c == '?') {
  116.             q[i].t = 3;
  117.             cin >> q[i].a >> q[i].b;
  118.             ZIP.ADD(q[i].a);
  119.             ZIP.ADD(q[i].a + 1);
  120.             ZIP.ADD(q[i].a - 1);
  121.             ZIP.ADD(q[i].b);
  122.             ZIP.ADD(q[i].b + 1);
  123.             ZIP.ADD(q[i].b - 1);
  124.         }
  125.     }
  126.  
  127.     ZIP.INIT();
  128.     int T = ZIP.v.size();
  129.     for (int i = 1; i <= N; i++) {
  130.         int tmp = ZIP.get(A[i]);
  131.         ST.update(1, 1, T, tmp, tmp, 1);
  132.     }
  133.     for (int i = 1; i <= Q; i++) {
  134.         if (q[i].t == 1) {
  135.             if (m[q[i].x]) {
  136.                 m[q[i].x]--;
  137.                 if (m[q[i].x] == 0) {
  138.                     int tmp = ZIP.get(q[i].x);
  139.                     ST.update(1, 1, T, tmp, tmp, 2);
  140.                 }
  141.             }
  142.         }
  143.         if (q[i].t == 2) {
  144.             m[q[i].x]++;
  145.             int tmp = ZIP.get(q[i].x);
  146.             ST.update(1, 1, T, tmp, tmp, 1);
  147.         }
  148.         if (q[i].t == 3) {
  149.             int tmp1 = ZIP.get(q[i].a - 1);
  150.             int tmp2 = ZIP.get(q[i].a);
  151.             int tmp3 = ZIP.get(q[i].b);
  152.             int tmp4 = ZIP.get(q[i].b + 1);
  153.  
  154.             ST.update(1, 1, T, tmp1, tmp1, 2);
  155.             ST.update(1, 1, T, tmp4, tmp4, 2);
  156.  
  157.             int res = ST.get(1, 1, T, tmp2, tmp3).ma;
  158.  
  159.             if (res == -oo) cout << 0 << '\n';
  160.             else cout << res << '\n';
  161.  
  162.             if (m[q[i].a - 1]) ST.update(1, 1, T, tmp1, tmp1, 1);
  163.             if (m[q[i].b + 1]) ST.update(1, 1, T, tmp4, tmp4, 1);
  164.         }
  165.     }
  166. }
  167.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/k3yE1w
language:
C++14 (gcc 8.3)
created:
5 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!