oj.uz

Submission #536742

# Submission time Handle Problem Language Result Execution time Memory
536742 2022-03-14T01:02:32 Z LucaDantas Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 19976 KB 
#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 = 1;
		for(; x > 0; x -= x&-x)
			ans += bit[x];
		return ans;
	}
	int bs(int x) {
		// quero achar o x-esimo cara ativo
		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++) bit[i] = i&-i; } // todo mundo ativado com 1
} bit;

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

vector<pair<int,int>> op;

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

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

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

		mx = max(mx, val);

		if(id > n) qr[id-n].e = val;
		else a[id] = val;
	}

	for(auto [id, e] : op)
		if(id > n) qr[id-n].e = mx-qr[id-n].e+1;
		else a[id] = mx-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 %d\n", l, r);
		printf("%d\n", r-l-1);
	}
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8116 KB Output is correct
2 Incorrect 5 ms 8148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 172 ms 19008 KB Output isn't correct
2 Correct 212 ms 19008 KB Output is correct
3 Correct 187 ms 18992 KB Output is correct
4 Correct 168 ms 18960 KB Output is correct
5 Incorrect 188 ms 19100 KB Output isn't correct
6 Correct 188 ms 19232 KB Output is correct
7 Correct 185 ms 19116 KB Output is correct
8 Correct 193 ms 19040 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 11908 KB Time limit exceeded
2 Execution timed out 2060 ms 11916 KB Time limit exceeded
3 Incorrect 1522 ms 11980 KB Output isn't correct
4 Incorrect 5 ms 8020 KB Output isn't correct
5 Execution timed out 2063 ms 14828 KB Time limit exceeded
6 Execution timed out 2061 ms 14768 KB Time limit exceeded
7 Execution timed out 2065 ms 14704 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 9312 KB Output isn't correct
2 Correct 74 ms 9316 KB Output is correct
3 Correct 799 ms 10932 KB Output is correct
4 Incorrect 803 ms 10844 KB Output isn't correct
5 Incorrect 116 ms 11396 KB Output isn't correct
6 Execution timed out 2084 ms 12812 KB Time limit exceeded
7 Correct 521 ms 12728 KB Output is correct
8 Correct 160 ms 14964 KB Output is correct
9 Execution timed out 2083 ms 19976 KB Time limit exceeded
10 Incorrect 376 ms 17980 KB Output isn't correct
11 Execution timed out 2086 ms 18524 KB Time limit exceeded
12 Execution timed out 2076 ms 19332 KB Time limit exceeded
13 Execution timed out 2078 ms 19960 KB Time limit exceeded