Submission #536750

#	Time	Username	Problem	Language	Result	Execution time	Memory
536750		LucaDantas	Cake (CEOI14_cake)	C++17	0 / 100	2089 ms	17540 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 = 0;
		for(; x > 0; x -= x&-x)
			ans += bit[x];
		return ans;
	}
	int bs(int x) {
		// quero achar o x-esimo cara ativo
		int l = 1, r = maxn-1, pos = 0;
		while(l <= r) {
			int m = (l+r) >> 1;
			if(this->query(m) < x)
				pos = m, l = m+1;
			else
				r = m-1;
		}
		return pos+1;

		/* 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++) this->upd(i, 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, a_ord;

int main() {
	int n, st; scanf("%d %d", &n, &st);
	for(int i = 1; i <= n; i++)
		scanf("%d", a+i), a_ord.push_back({n-a[i]+1, i});
	
	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({i, qr[i].e});
		} else {
			int x; scanf("%d", &x);
			qr[i] = {x, -1};
		}
	}

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

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

		qr[id].e = val;
	}

	sort(a_ord.begin(), a_ord.end());
	for(auto [val, id] : a_ord)
		a[id] = bit.bs(1), bit.upd(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\n", r-l-1);
	}
}

Compilation message (stderr)

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

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