oj.uz

Submission #536744

# Submission time Handle Problem Language Result Execution time Memory
536744 2022-03-14T01:06:38 Z LucaDantas Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 17288 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 5 ms 8148 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 165 ms 16144 KB Output isn't correct
2 Correct 159 ms 16152 KB Output is correct
3 Correct 163 ms 16168 KB Output is correct
4 Correct 172 ms 16172 KB Output is correct
5 Incorrect 177 ms 16268 KB Output isn't correct
6 Correct 166 ms 16300 KB Output is correct
7 Correct 175 ms 16388 KB Output is correct
8 Correct 173 ms 16444 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2097 ms 10636 KB Time limit exceeded
2 Execution timed out 2100 ms 10620 KB Time limit exceeded
3 Incorrect 1744 ms 10744 KB Output isn't correct
4 Incorrect 5 ms 8020 KB Output isn't correct
5 Execution timed out 2087 ms 12284 KB Time limit exceeded
6 Execution timed out 2097 ms 12092 KB Time limit exceeded
7 Execution timed out 2060 ms 12216 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 8924 KB Output isn't correct
2 Correct 73 ms 9032 KB Output is correct
3 Correct 786 ms 10060 KB Output is correct
4 Incorrect 770 ms 10036 KB Output isn't correct
5 Incorrect 112 ms 10344 KB Output isn't correct
6 Execution timed out 2096 ms 11240 KB Time limit exceeded
7 Correct 510 ms 11240 KB Output is correct
8 Correct 156 ms 12468 KB Output is correct
9 Execution timed out 2075 ms 17288 KB Time limit exceeded
10 Incorrect 366 ms 15220 KB Output isn't correct
11 Execution timed out 2090 ms 15716 KB Time limit exceeded
12 Execution timed out 2091 ms 16660 KB Time limit exceeded
13 Execution timed out 2091 ms 17236 KB Time limit exceeded