oj.uz

Submission #492573

# Submission time Handle Problem Language Result Execution time Memory
492573 2021-12-08T02:05:05 Z ntabc05101 Cake (CEOI14_cake) C++14
100 / 100
 669 ms 22328 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, bool> 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()[0] + 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 11 ms 1616 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 3356 KB Output is correct
2 Correct 210 ms 5396 KB Output is correct
3 Correct 223 ms 5452 KB Output is correct
4 Correct 139 ms 5388 KB Output is correct
5 Correct 355 ms 6528 KB Output is correct
6 Correct 304 ms 4404 KB Output is correct
7 Correct 249 ms 10656 KB Output is correct
8 Correct 138 ms 10548 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9484 KB Output is correct
2 Correct 59 ms 9424 KB Output is correct
3 Correct 51 ms 9384 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 98 ms 19248 KB Output is correct
6 Correct 93 ms 19228 KB Output is correct
7 Correct 66 ms 19040 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 960 KB Output is correct
2 Correct 29 ms 1212 KB Output is correct
3 Correct 55 ms 5444 KB Output is correct
4 Correct 79 ms 5420 KB Output is correct
5 Correct 128 ms 1904 KB Output is correct
6 Correct 128 ms 7016 KB Output is correct
7 Correct 108 ms 2628 KB Output is correct
8 Correct 117 ms 12284 KB Output is correct
9 Correct 615 ms 22328 KB Output is correct
10 Correct 376 ms 3676 KB Output is correct
11 Correct 479 ms 7748 KB Output is correct
12 Correct 669 ms 21032 KB Output is correct
13 Correct 483 ms 21804 KB Output is correct