Submission #536742

#	Time	Username	Problem	Language	Result	Execution time	Memory
536742		LucaDantas	Cake (CEOI14_cake)	C++17	0 / 100	2086 ms	19976 KiB

cake

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 2e6+10, logn = 22;

int a[maxn];

struct BIT {
	int bit[maxn];
	void upd(int x, int v) {
		for(; x < maxn; x += x&-x)
			bit[x] += v;
	}
	int query(int x) {
		int ans = 1;
		for(; x > 0; x -= x&-x)
			ans += bit[x];
		return ans;
	}
	int bs(int x) {
		// quero achar o x-esimo cara ativo
		int pos = 0;
		for(int l = logn-1; l >= 0; l--) {
			if(pos + (1 << l) >= maxn) continue;
			if(bit[pos + (1 << l)] < x)
				x -= bit[pos + (1 << l)], pos += 1<<l;
		}
		return pos+1;
	}
	void fill() { for(int i = 1; i < maxn; i++) bit[i] = i&-i; } // todo mundo ativado com 1
} bit;

struct Query { int x, e; } qr[maxn];

vector<pair<int,int>> op;

int main() {
	int n, st; scanf("%d %d", &n, &st);
	for(int i = 1; i <= n; i++)
		scanf("%d", a+i), op.push_back({i, n-a[i]+1});
	
	int q; scanf("%d", &q);
	for(int i = 1; i <= q; i++) {
		char c; scanf(" %c", &c);
		if(c == 'E') {
			scanf("%d %d", &qr[i].x, &qr[i].e);
			op.push_back({n+i, qr[i].e});
		} else {
			int x; scanf("%d", &x);
			qr[i] = {x, -1};
		}
	}

	reverse(op.begin(), op.end());

	bit.fill();
	int mx = 0;
	for(auto [id, e] : op) {
		int val = bit.bs(e);
		bit.upd(val, -1); // removo esse cara

		mx = max(mx, val);

		if(id > n) qr[id-n].e = val;
		else a[id] = val;
	}

	for(auto [id, e] : op)
		if(id > n) qr[id-n].e = mx-qr[id-n].e+1;
		else a[id] = mx-a[id]+1;

	a[0] = 0x3f3f3f3f;
	a[n+1] = 0x3f3f3f3f;

	for(int i = 1; i <= q; i++) {
		auto [x, val] = qr[i];
		if(val != -1) { a[x] = val; continue; }
		if(x == st) { puts("0"); continue; }

		int l = st-1, r = st+1;
		
		while(l != x && r != x)
			if(a[l] < a[r]) l--;
			else r++;
		
		while(l != x && a[l] < a[r])
			--l;
		
		while(r != x && a[r] < a[l])
			++r;

		// printf("%d %d\n", l, r);
		printf("%d\n", r-l-1);
	}
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:38:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  int n, st; scanf("%d %d", &n, &st);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d", a+i), op.push_back({i, n-a[i]+1});
      |   ~~~~~^~~~~~~~~~~
cake.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
cake.cpp:44:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   char c; scanf(" %c", &c);
      |           ~~~~~^~~~~~~~~~~
cake.cpp:46:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |    scanf("%d %d", &qr[i].x, &qr[i].e);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:49:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50