oj.uz

Submission #492451

# Submission time Handle Problem Language Result Execution time Memory
492451 2021-12-07T12:07:49 Z ntabc05101 Cake (CEOI14_cake) C++14
0 / 100
 291 ms 19756 KB 
#include<bits/stdc++.h>
using namespace std;

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 0;
    }
    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 >= 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 >= l && nds[x].H <= r) {
      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];

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]];
    //cout << a[i] << " ";
  }
  its.build(1, 0, n - 1);
  //cout << its.nds[1].x << "\n";
  char type; int e, x;
  while (--q) {
    cin >> type >> x; x--;
    if (type == 'E') {
      cin >> e;
      cur[n - e]++;
      //cout << x << " " << cur[n - e] << "\n";
      its.upd(x, cur[n - e]);
    }
    else {
      if (x == A) {
        cout << "0\n";
      }
      else {
        if (A == 0 || A == n - 1) {
          cout << abs(x - A) << "\n";
        }
        else {
          if (x > A) {
            //cout << its.get_mx(A + 1, x) << " ";
            //cout << its.get_pos1(0, A - 1, its.get_mx(A + 1, x)) << " ";
            cout << x - 1 - its.get_pos1(0, A - 1, its.get_mx(A + 1, x)) << "\n";
          }
          else {
            /*cout << its.get_mx(x, A - 1) << " ";
            cout << its.get_pos2(A + 1, n - 1, 0) << " ";*/
            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 332 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 104 ms 1904 KB Output isn't correct
2 Correct 94 ms 1916 KB Output is correct
3 Incorrect 119 ms 1920 KB Output isn't correct
4 Correct 91 ms 1856 KB Output is correct
5 Incorrect 120 ms 2872 KB Output isn't correct
6 Incorrect 121 ms 2988 KB Output isn't correct
7 Incorrect 113 ms 2988 KB Output isn't correct
8 Correct 104 ms 3012 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 9604 KB Output isn't correct
2 Incorrect 60 ms 9512 KB Output isn't correct
3 Incorrect 60 ms 9472 KB Output isn't correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Incorrect 82 ms 18712 KB Output isn't correct
6 Incorrect 80 ms 18764 KB Output isn't correct
7 Incorrect 63 ms 18456 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 1100 KB Output isn't correct
2 Incorrect 18 ms 1344 KB Output isn't correct
3 Incorrect 37 ms 5188 KB Output isn't correct
4 Incorrect 35 ms 5188 KB Output isn't correct
5 Incorrect 46 ms 1420 KB Output isn't correct
6 Incorrect 69 ms 5676 KB Output isn't correct
7 Incorrect 66 ms 2404 KB Output isn't correct
8 Incorrect 63 ms 9000 KB Output isn't correct
9 Incorrect 291 ms 19756 KB Output isn't correct
10 Incorrect 144 ms 2204 KB Output isn't correct
11 Incorrect 189 ms 4164 KB Output isn't correct
12 Incorrect 271 ms 18756 KB Output isn't correct
13 Incorrect 222 ms 19720 KB Output isn't correct