oj.uz

Submission #536750

# Submission time Handle Problem Language Result Execution time Memory
536750 2022-03-14T01:24:03 Z LucaDantas Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 17540 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, a_ord;

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

		qr[id].e = val;
	}

	sort(a_ord.begin(), a_ord.end());
	for(auto [val, id] : a_ord)
		a[id] = bit.bs(1), bit.upd(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\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), a_ord.push_back({n-a[i]+1, i});
      |   ~~~~~^~~~~~~~~~~
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 41 ms 8044 KB Output is correct
2 Incorrect 40 ms 8092 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 309 ms 16188 KB Output isn't correct
2 Correct 306 ms 16220 KB Output is correct
3 Correct 299 ms 16228 KB Output is correct
4 Correct 301 ms 16292 KB Output is correct
5 Incorrect 313 ms 16508 KB Output isn't correct
6 Correct 304 ms 16484 KB Output is correct
7 Correct 304 ms 16420 KB Output is correct
8 Correct 318 ms 16440 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 10592 KB Time limit exceeded
2 Execution timed out 2077 ms 10820 KB Time limit exceeded
3 Correct 1766 ms 10752 KB Output is correct
4 Incorrect 39 ms 8012 KB Output isn't correct
5 Execution timed out 2088 ms 12336 KB Time limit exceeded
6 Execution timed out 2072 ms 12384 KB Time limit exceeded
7 Execution timed out 2070 ms 12392 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 9032 KB Output isn't correct
2 Correct 116 ms 9112 KB Output is correct
3 Correct 886 ms 10040 KB Output is correct
4 Correct 881 ms 10076 KB Output is correct
5 Incorrect 163 ms 10392 KB Output isn't correct
6 Execution timed out 2069 ms 11404 KB Time limit exceeded
7 Correct 584 ms 11264 KB Output is correct
8 Correct 253 ms 12624 KB Output is correct
9 Execution timed out 2089 ms 17456 KB Time limit exceeded
10 Incorrect 456 ms 15288 KB Output isn't correct
11 Execution timed out 2080 ms 15640 KB Time limit exceeded
12 Execution timed out 2080 ms 16792 KB Time limit exceeded
13 Execution timed out 2086 ms 17540 KB Time limit exceeded