oj.uz

Submission #492572

# Submission time Handle Problem Language Result Execution time Memory
492572 2021-12-08T02:01:02 Z ntabc05101 Cake (CEOI14_cake) C++14
0 / 100
 627 ms 22268 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];
int pos[mxN];
map<int, int> lst;
vector< array<int, 2> > top;

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]--;
		pos[a[i]] = i;
  }
	for (int i = 0; i < n; i++) {
		top.push_back({i, pos[i]});
	}
  
  int q; cin >> q;
  q++;
  its.build(1, 0, n - 1);
  char type; int e, x;
  while (--q) {
    cin >> type >> x; x--;
    if (type == 'E') {
      cin >> e; e--;

			deque< array<int, 2> > deq;
			lst.clear();
			lst[x] = 1;
			while (deq.size() < e) {
				if (lst.find(top.back()[1]) == lst.end()) {
					lst[top.back()[1]] = 1;
					deq.push_front(top.back()); 
				}
				top.pop_back();
			}

			its.upd(x, top.back()[0] + 1);
			top.push_back({top.back()[0] + 1, x});
			while (!deq.empty()) {
				its.upd(deq.front()[1], top.back()[0] + 1);
				top.push_back({top.back()[1] + 1, deq.front()[1]});
				deq.pop_front();
			}
    }
    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;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:136:22: warning: comparison of integer expressions of different signedness: 'std::deque<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |    while (deq.size() < e) {
      |           ~~~~~~~~~~~^~~

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 352 ms 3436 KB Output isn't correct
2 Incorrect 201 ms 5560 KB Output isn't correct
3 Incorrect 222 ms 5448 KB Output isn't correct
4 Correct 129 ms 5456 KB Output is correct
5 Incorrect 358 ms 6648 KB Output isn't correct
6 Incorrect 298 ms 4468 KB Output isn't correct
7 Incorrect 234 ms 10712 KB Output isn't correct
8 Correct 138 ms 10668 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 9512 KB Output isn't correct
2 Incorrect 50 ms 9284 KB Output isn't correct
3 Incorrect 44 ms 9124 KB Output isn't correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 91 ms 19176 KB Output isn't correct
6 Incorrect 88 ms 19292 KB Output isn't correct
7 Incorrect 63 ms 18752 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 964 KB Output isn't correct
2 Incorrect 25 ms 1236 KB Output isn't correct
3 Incorrect 55 ms 5452 KB Output isn't correct
4 Incorrect 76 ms 5404 KB Output isn't correct
5 Incorrect 108 ms 1836 KB Output isn't correct
6 Incorrect 105 ms 7000 KB Output isn't correct
7 Incorrect 104 ms 2624 KB Output isn't correct
8 Incorrect 121 ms 12216 KB Output isn't correct
9 Incorrect 627 ms 22268 KB Output isn't correct
10 Incorrect 361 ms 3700 KB Output isn't correct
11 Incorrect 434 ms 7772 KB Output isn't correct
12 Incorrect 601 ms 21168 KB Output isn't correct
13 Incorrect 462 ms 21884 KB Output isn't correct