oj.uz

Submission #492565

# Submission time Handle Problem Language Result Execution time Memory
492565 2021-12-08T01:10:14 Z ntabc05101 Cake (CEOI14_cake) C++14
0 / 100
 801 ms 34780 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(a[x]));
			y++; its.upd(x, y);
			a[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 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 230 ms 1828 KB Output isn't correct
2 Incorrect 266 ms 1916 KB Output isn't correct
3 Incorrect 225 ms 1996 KB Output isn't correct
4 Correct 322 ms 1920 KB Output is correct
5 Incorrect 347 ms 3876 KB Output isn't correct
6 Incorrect 263 ms 3916 KB Output isn't correct
7 Incorrect 304 ms 3916 KB Output isn't correct
8 Correct 406 ms 3920 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 15312 KB Output isn't correct
2 Incorrect 90 ms 15108 KB Output isn't correct
3 Incorrect 87 ms 14988 KB Output isn't correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Correct 317 ms 33716 KB Output is correct
6 Incorrect 266 ms 33832 KB Output isn't correct
7 Incorrect 168 ms 33508 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 832 KB Output isn't correct
2 Incorrect 29 ms 1200 KB Output isn't correct
3 Incorrect 97 ms 7688 KB Output isn't correct
4 Incorrect 83 ms 7672 KB Output isn't correct
5 Incorrect 65 ms 888 KB Output isn't correct
6 Incorrect 169 ms 9160 KB Output isn't correct
7 Incorrect 110 ms 2316 KB Output isn't correct
8 Incorrect 224 ms 14660 KB Output isn't correct
9 Incorrect 801 ms 34780 KB Output isn't correct
10 Incorrect 196 ms 1584 KB Output isn't correct
11 Incorrect 254 ms 4856 KB Output isn't correct
12 Incorrect 739 ms 30628 KB Output isn't correct
13 Incorrect 543 ms 34768 KB Output isn't correct