oj.uz

Submission #492435

# Submission time Handle Problem Language Result Execution time Memory
492435 2021-12-07T10:17:43 Z ntabc05101 Cake (CEOI14_cake) C++14
0 / 100
 226 ms 25416 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;
    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) {
    if (lo == hi) {
      nds[x].L = lo, nds[x].H = 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]);
    nds[x].L = lo, nds[x].H = hi;
  }
  
  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]++;
      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 << 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 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 137 ms 5596 KB Output isn't correct
2 Incorrect 118 ms 5600 KB Output isn't correct
3 Incorrect 112 ms 5828 KB Output isn't correct
4 Incorrect 98 ms 5812 KB Output isn't correct
5 Incorrect 135 ms 6936 KB Output isn't correct
6 Incorrect 116 ms 7348 KB Output isn't correct
7 Incorrect 123 ms 7108 KB Output isn't correct
8 Incorrect 106 ms 7356 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 10300 KB Output isn't correct
2 Incorrect 29 ms 10244 KB Output isn't correct
3 Incorrect 32 ms 10136 KB Output isn't correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Incorrect 59 ms 20500 KB Output isn't correct
6 Incorrect 59 ms 20520 KB Output isn't correct
7 Incorrect 51 ms 20516 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1100 KB Output isn't correct
2 Incorrect 12 ms 1348 KB Output isn't correct
3 Incorrect 27 ms 5496 KB Output isn't correct
4 Incorrect 24 ms 5452 KB Output isn't correct
5 Incorrect 32 ms 1912 KB Output isn't correct
6 Incorrect 46 ms 6676 KB Output isn't correct
7 Incorrect 48 ms 3272 KB Output isn't correct
8 Incorrect 74 ms 10948 KB Output isn't correct
9 Incorrect 226 ms 25416 KB Output isn't correct
10 Incorrect 111 ms 5264 KB Output isn't correct
11 Incorrect 160 ms 7860 KB Output isn't correct
12 Incorrect 204 ms 24072 KB Output isn't correct
13 Incorrect 160 ms 25376 KB Output isn't correct