oj.uz

Submission #536754

# Submission time Handle Problem Language Result Execution time Memory
536754 2022-03-14T01:41:52 Z LucaDantas Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 17148 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;
			for(int k = 1; k < pos; k++) {
				int id = ord.begin()->second;
				ord.erase(ord.begin());
				val = a[id];
				++a[id];
				ord.insert({a[id], id});
			}
			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

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 289 ms 4672 KB Output isn't correct
2 Incorrect 204 ms 4688 KB Output isn't correct
3 Incorrect 273 ms 4696 KB Output isn't correct
4 Correct 207 ms 4684 KB Output is correct
5 Incorrect 306 ms 5460 KB Output isn't correct
6 Incorrect 354 ms 5508 KB Output isn't correct
7 Incorrect 248 ms 5512 KB Output isn't correct
8 Correct 243 ms 5488 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 6596 KB Time limit exceeded
2 Execution timed out 2040 ms 6508 KB Time limit exceeded
3 Incorrect 1666 ms 6832 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Execution timed out 2087 ms 13948 KB Time limit exceeded
6 Execution timed out 2077 ms 13984 KB Time limit exceeded
7 Execution timed out 2084 ms 14044 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 928 KB Output isn't correct
2 Incorrect 77 ms 1068 KB Output isn't correct
3 Incorrect 907 ms 3696 KB Output isn't correct
4 Incorrect 864 ms 3716 KB Output isn't correct
5 Incorrect 153 ms 1800 KB Output isn't correct
6 Execution timed out 2088 ms 5256 KB Time limit exceeded
7 Incorrect 560 ms 2940 KB Output isn't correct
8 Incorrect 230 ms 6968 KB Output isn't correct
9 Execution timed out 2099 ms 17044 KB Time limit exceeded
10 Incorrect 489 ms 5380 KB Output isn't correct
11 Execution timed out 2081 ms 6228 KB Time limit exceeded
12 Execution timed out 2070 ms 14568 KB Time limit exceeded
13 Execution timed out 2071 ms 17148 KB Time limit exceeded