oj.uz

Submission #492564

# Submission time Handle Problem Language Result Execution time Memory
492564 2021-12-08T01:07:40 Z ntabc05101 Cake (CEOI14_cake) C++14
0 / 100
 574 ms 37956 KB 
#include<bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<long long, null_type,greater<long long>, rb_tree_tag,tree_order_statistics_node_update>

const int mxN = 250001;

int n, A;
long long a[mxN];

struct IT {
  struct Nds {
    int L, H, pos;
    long long x;
  } nds[mxN << 2];
  int leaf[mxN];
  
  Nds merge(Nds a, Nds b) {
    Nds c;
    c.L = a.L; c.H = b.H;
    if (a.x >= b.x + (a.L < A)) {
      c.x = a.x; c.pos = a.pos;
    }
    else {
      c.x = b.x; c.pos = b.pos;
    }
    return c;
  }
  
  void build(int x, int lo, int hi) {
    nds[x].L = lo, nds[x].H = hi;
    if (lo == hi) {
      leaf[hi] = x;
      nds[x].x = a[hi];
      nds[x].pos = hi;
      return ;
    }
    
    int mid = (lo + hi) >> 1;
    build(x << 1, lo, mid);
    build(x << 1 | 1, mid + 1, hi);
    
    nds[x] = merge(nds[x << 1], nds[x << 1 | 1]);
  }
  
  void upd(int pos, long long val) {
    int x = leaf[pos];
    for (nds[x].x = val, x >>= 1; x; x >>= 1) {
      nds[x] = merge(nds[x << 1], nds[x << 1 | 1]);
    }
  }
  
  long long get_mx(int l, int r, int x = 1) {
    if (nds[x].L > r || nds[x].H < l) {
      return -1;
    }
    if (nds[x].L >= l && nds[x].H <= r) {
      return nds[x].x;
    }
    return max(get_mx(l, r, x << 1), get_mx(l, r, x << 1 | 1));
  }
  
  int get_pos1(int l, int r, long long val, int x = 1) {
    if (nds[x].L > r || nds[x].H < l) {
      return -1;
    }
    if (nds[x].x < val) {
      return -1;
    }
    if (nds[x].L == nds[x].H) {
      return nds[x].pos;
    }
    /*if (nds[x].L >= l && nds[x].H <= r) {
      return nds[x].pos;
    }*/
    
    int res = get_pos1(l, r, val, x << 1 | 1);
    if (res >= 0) {
      return res;
    }
    return get_pos1(l, r, val, x << 1);
  }
  
  int get_pos2(int l, int r, long long val, int x = 1) {
    if (nds[x].L > r || nds[x].H < l) {
      return n;
    }
    if (nds[x].x < val) {
      return n;
    }
    if (nds[x].L == nds[x].H) {
      return nds[x].pos;
    }
    
    int res = get_pos2(l, r, val, x << 1);
    if (res < n) {
      return res;
    }
    return get_pos2(l, r, val, x << 1 | 1);
  }
} its;

long long cur[mxN];
ordered_set oset;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  
  cin >> n >> A; A--;
  for (int i = 0; i < n; i++) {
    cin >> a[i]; a[i]--;
  }
  
  int q; cin >> q;
  q++;
  for (int i = 0; i < n; i++) {
    cur[a[i]] = a[i] * q;
    a[i] = cur[a[i]];
		oset.insert(a[i]);
  }
  its.build(1, 0, n - 1);
  char type; int e, x;
  while (--q) {
    cin >> type >> x; x--;
    if (type == 'E') {
      cin >> e; e--;
			long long y = *oset.find_by_order(e);
			oset.erase(oset.find(y));
			y++; its.upd(x, y);
			oset.insert(y);
    }
    else {
      if (x == A) {
        cout << "0\n";
      }
      else {
        if (A == 0 || A == n - 1) {
          cout << abs(x - A) << "\n";
        }
        else {
          if (x > A) {
            cout << x - 1 - its.get_pos1(0, A - 1, its.get_mx(A + 1, x)) << "\n";
          }
          else {
            cout << its.get_pos2(A + 1, n - 1, its.get_mx(x, A - 1)) - x - 1 << "\n";
          }
        }
      }
    }
  }
  
  return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 4880 KB Output isn't correct
2 Correct 329 ms 4832 KB Output is correct
3 Incorrect 188 ms 4844 KB Output isn't correct
4 Correct 325 ms 4860 KB Output is correct
5 Incorrect 230 ms 6820 KB Output isn't correct
6 Incorrect 427 ms 6860 KB Output isn't correct
7 Incorrect 211 ms 6996 KB Output isn't correct
8 Correct 419 ms 6868 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 16596 KB Output isn't correct
2 Incorrect 91 ms 16436 KB Output isn't correct
3 Incorrect 89 ms 16376 KB Output isn't correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Incorrect 260 ms 36324 KB Output isn't correct
6 Incorrect 236 ms 36164 KB Output isn't correct
7 Incorrect 166 ms 35992 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 1220 KB Output isn't correct
2 Incorrect 28 ms 1560 KB Output isn't correct
3 Incorrect 69 ms 8540 KB Output isn't correct
4 Incorrect 88 ms 8548 KB Output isn't correct
5 Incorrect 66 ms 1908 KB Output isn't correct
6 Incorrect 117 ms 10788 KB Output isn't correct
7 Incorrect 94 ms 3992 KB Output isn't correct
8 Incorrect 147 ms 17180 KB Output isn't correct
9 Incorrect 574 ms 37956 KB Output isn't correct
10 Incorrect 213 ms 4548 KB Output isn't correct
11 Incorrect 266 ms 7796 KB Output isn't correct
12 Incorrect 500 ms 33596 KB Output isn't correct
13 Incorrect 483 ms 37748 KB Output isn't correct