oj.uz

Submission #536747

# Submission time Handle Problem Language Result Execution time Memory
536747 2022-03-14T01:13:24 Z LucaDantas Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 17544 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 = 0;
		for(; x > 0; x -= x&-x)
			ans += bit[x];
		return ans;
	}
	int bs(int x) {
		// quero achar o x-esimo cara ativo
		int l = 1, r = maxn-1, pos = 0;
		while(l <= r) {
			int m = (l+r) >> 1;
			if(this->query(m) < x)
				pos = m, l = m+1;
			else
				r = m-1;
		}
		return pos+1;

		/* 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++) this->upd(i, 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();
	for(auto [id, e] : op) {
		int val = bit.bs(e);
		bit.upd(val, -1); // removo esse cara

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

	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\n", r-l-1);
	}
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 8124 KB Output is correct
2 Incorrect 51 ms 8140 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 315 ms 16080 KB Output isn't correct
2 Correct 317 ms 16136 KB Output is correct
3 Correct 329 ms 16196 KB Output is correct
4 Correct 318 ms 16204 KB Output is correct
5 Incorrect 365 ms 16304 KB Output isn't correct
6 Correct 316 ms 16460 KB Output is correct
7 Correct 338 ms 16328 KB Output is correct
8 Correct 308 ms 16320 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2089 ms 10512 KB Time limit exceeded
2 Execution timed out 2077 ms 10724 KB Time limit exceeded
3 Incorrect 1570 ms 10712 KB Output isn't correct
4 Incorrect 39 ms 8012 KB Output isn't correct
5 Execution timed out 2078 ms 12280 KB Time limit exceeded
6 Execution timed out 2088 ms 12196 KB Time limit exceeded
7 Execution timed out 2069 ms 12504 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 9000 KB Output isn't correct
2 Correct 114 ms 9064 KB Output is correct
3 Correct 913 ms 9860 KB Output is correct
4 Incorrect 919 ms 10152 KB Output isn't correct
5 Incorrect 170 ms 10304 KB Output isn't correct
6 Execution timed out 2074 ms 11392 KB Time limit exceeded
7 Correct 596 ms 11164 KB Output is correct
8 Correct 265 ms 12464 KB Output is correct
9 Execution timed out 2092 ms 17224 KB Time limit exceeded
10 Incorrect 470 ms 15328 KB Output isn't correct
11 Execution timed out 2081 ms 15576 KB Time limit exceeded
12 Execution timed out 2081 ms 16716 KB Time limit exceeded
13 Execution timed out 2083 ms 17544 KB Time limit exceeded