oj.uz

Submission #537317

# Submission time Handle Problem Language Result Execution time Memory
537317 2022-03-15T01:00:05 Z LucaDantas Cake (CEOI14_cake) C++17
30 / 100
 2000 ms 16948 KB 
#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; }

		vector<int> l, r; // salvo os dois paretos

		for(int i = st+1; i <= n; i++)
			if(!r.size() || a[i] > a[r.back()])
				r.push_back(i);
		r.push_back(n+1); a[n+1] = 0x3f3f3f3f;

		for(int i = st-1; i >= 1; i--)
			if(!l.size() || a[i] > a[l.back()])
				l.push_back(i);
		l.push_back(0); a[0] = 0x3f3f3f3f;

		// query
		if(x == st) puts("0");
		else if(x > st) {
			auto mx = *(--upper_bound(r.begin(), r.end(), x));

			int L = 0, R = (int)(l.size())-1, ans = 1;
			while(L <= R) {
				int M = (L+R) >> 1;
				if(a[l[M]] > a[mx])
					ans = l[M]+1, R = M-1;
				else
					L = M+1;
			}

			printf("%d\n", x - ans); // não inclui x

		} else {
			auto mx = *lower_bound(l.rbegin(), l.rend(), x);

			int L = 0, R = (int)(r.size())-1, ans = n;
			while(L <= R) {
				int M = (L+R) >> 1;
				if(a[r[M]] > a[mx])
					ans = r[M]-1, R = M-1;
				else
					L = M+1;
			}

			printf("%d\n", ans - x); // não inclui x
		}

	}
}

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 340 KB Output is correct
5 Correct 151 ms 904 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 4736 KB Output is correct
2 Correct 265 ms 4720 KB Output is correct
3 Correct 293 ms 4720 KB Output is correct
4 Correct 216 ms 4724 KB Output is correct
5 Correct 437 ms 5584 KB Output is correct
6 Correct 380 ms 5536 KB Output is correct
7 Correct 320 ms 5480 KB Output is correct
8 Correct 299 ms 5436 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2087 ms 6440 KB Time limit exceeded
2 Execution timed out 2093 ms 6424 KB Time limit exceeded
3 Execution timed out 2094 ms 6308 KB Time limit exceeded
4 Correct 0 ms 212 KB Output is correct
5 Execution timed out 2084 ms 13808 KB Time limit exceeded
6 Execution timed out 2098 ms 13812 KB Time limit exceeded
7 Execution timed out 2094 ms 13904 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 928 KB Output is correct
2 Correct 361 ms 948 KB Output is correct
3 Execution timed out 2094 ms 3620 KB Time limit exceeded
4 Execution timed out 2071 ms 3688 KB Time limit exceeded
5 Correct 535 ms 1856 KB Output is correct
6 Execution timed out 2096 ms 4860 KB Time limit exceeded
7 Execution timed out 2075 ms 2984 KB Time limit exceeded
8 Correct 725 ms 6964 KB Output is correct
9 Execution timed out 2097 ms 16944 KB Time limit exceeded
10 Correct 1760 ms 5448 KB Output is correct
11 Execution timed out 2081 ms 5596 KB Time limit exceeded
12 Execution timed out 2089 ms 14608 KB Time limit exceeded
13 Execution timed out 2091 ms 16948 KB Time limit exceeded