oj.uz

Submission #536755

# Submission time Handle Problem Language Result Execution time Memory
536755 2022-03-14T01:44:32 Z LucaDantas Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 17248 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 0 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 283 ms 4564 KB Output isn't correct
2 Incorrect 200 ms 4656 KB Output isn't correct
3 Incorrect 235 ms 4684 KB Output isn't correct
4 Correct 173 ms 4772 KB Output is correct
5 Incorrect 309 ms 5464 KB Output isn't correct
6 Incorrect 273 ms 5764 KB Output isn't correct
7 Incorrect 247 ms 5580 KB Output isn't correct
8 Correct 223 ms 5452 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2087 ms 6724 KB Time limit exceeded
2 Execution timed out 2061 ms 6716 KB Time limit exceeded
3 Incorrect 1570 ms 6776 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Execution timed out 2086 ms 14244 KB Time limit exceeded
6 Execution timed out 2088 ms 14192 KB Time limit exceeded
7 Execution timed out 2093 ms 14272 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 852 KB Output isn't correct
2 Incorrect 77 ms 1096 KB Output isn't correct
3 Incorrect 804 ms 3608 KB Output isn't correct
4 Incorrect 809 ms 3624 KB Output isn't correct
5 Incorrect 139 ms 1884 KB Output isn't correct
6 Execution timed out 2086 ms 5380 KB Time limit exceeded
7 Incorrect 544 ms 2836 KB Output isn't correct
8 Incorrect 220 ms 6892 KB Output isn't correct
9 Execution timed out 2079 ms 16984 KB Time limit exceeded
10 Incorrect 449 ms 5380 KB Output isn't correct
11 Execution timed out 2087 ms 6396 KB Time limit exceeded
12 Execution timed out 2090 ms 14712 KB Time limit exceeded
13 Execution timed out 2093 ms 17248 KB Time limit exceeded