Submission #537314

#	Time	Username	Problem	Language	Result	Execution time	Memory
537314		LucaDantas	Cake (CEOI14_cake)	C++17	46.67 / 100	2098 ms	17140 KiB

cake

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

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

int a[maxn];

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

set<pair<int,int>, greater<pair<int,int>>> ord;

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

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

	for(int i = 1; i <= q; i++) {
		auto [x, pos] = qr[i];
		if(pos != -1) {
			int val = ord.begin()->first+1;
			
			vector<pair<int,int>> add;
			for(int k = 1; k < pos; k++) {
				int id = ord.begin()->second;
				ord.erase(ord.begin());
				val = a[id];
				++a[id];
				add.push_back({a[id], id});
			}
			
			for(auto p : add)
				ord.insert(p);

			assert(ord.find({a[x], x}) != ord.end());
			ord.erase({a[x], x});
			a[x] = val;
			ord.insert({a[x], x});

			/* for(int i = 1; i <= n; i++)
				printf("%d ", a[i]);
			puts(""); */
			
			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:13:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  int n, st; scanf("%d %d", &n, &st);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d", a+i), ord.insert({a[i], i});
      |   ~~~~~^~~~~~~~~~~
cake.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
cake.cpp:19:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   char c; scanf(" %c", &c);
      |           ~~~~~^~~~~~~~~~~
cake.cpp:21:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |    scanf("%d %d", &qr[i].x, &qr[i].e);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:23:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~

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