Submission #492573

#	Time	Username	Problem	Language	Result	Execution time	Memory
492573		ntabc05101	Cake (CEOI14_cake)	C++14	100 / 100	669 ms	22328 KiB

cake

#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 (stderr)

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50