oj.uz

Submission #536745

# Submission time Handle Problem Language Result Execution time Memory
536745 2022-03-14T01:08:52 Z LucaDantas Cake (CEOI14_cake) C++17
0 / 100
 290 ms 18784 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 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;

	vector<int> l, r; // salvo os dois paretos

	for(int i = st+1; i <= n; i++)
		if(!r.size() || a[i] > a[r.back()])
			r.push_back(i);
	r.push_back(n+1); a[n+1] = 0x3f3f3f3f;

	for(int i = st-1; i >= 1; i--)
		if(!l.size() || a[i] > a[l.back()])
			l.push_back(i);
	l.push_back(0); a[0] = 0x3f3f3f3f;

	for(int i = 1; i <= q; i++) {
		if(qr[i].e == -1) {

			// query
			int x = qr[i].x;

			if(x == st) puts("0");
			else if(x > st) {
				auto mx = *(--upper_bound(r.begin(), r.end(), x));

				int L = 0, R = (int)(l.size())-1, ans = 1;
				while(L <= R) {
					int M = (L+R) >> 1;
					if(a[l[M]] > a[mx])
						ans = l[M]+1, R = M-1;
					else
						L = M+1;
				}

				printf("%d\n", x - ans); // não inclui x

			} else {
				auto mx = *lower_bound(l.rbegin(), l.rend(), x);

				int L = 0, R = (int)(r.size())-1, ans = n;
				while(L <= R) {
					int M = (L+R) >> 1;
					if(a[r[M]] > a[mx])
						ans = r[M]-1, R = M-1;
					else
						L = M+1;
				}

				printf("%d\n", ans - x); // não inclui x
			}
		} else {
			// upd
			auto [x, val] = qr[i];
			a[x] = val;

			if(x < st) swap(l, r);
			
			vector<int> sv = {x};
			while(r.size() && (x > st ? r.back() > x : r.back() < x))
				sv.push_back(r.back()), r.pop_back();
			for(int x : sv)
				if(!r.size() || a[x] > a[r.back()])
					r.push_back(x);

			if(x < st) swap(l, r);

		}
	}
}

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 208 ms 16188 KB Output isn't correct
2 Correct 197 ms 16196 KB Output is correct
3 Incorrect 201 ms 16200 KB Output isn't correct
4 Correct 188 ms 16168 KB Output is correct
5 Incorrect 212 ms 16292 KB Output isn't correct
6 Incorrect 231 ms 16316 KB Output isn't correct
7 Incorrect 216 ms 16388 KB Output isn't correct
8 Correct 201 ms 16268 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 10740 KB Output isn't correct
2 Incorrect 51 ms 10608 KB Output isn't correct
3 Incorrect 47 ms 10556 KB Output isn't correct
4 Incorrect 5 ms 8148 KB Output isn't correct
5 Incorrect 118 ms 12592 KB Output isn't correct
6 Incorrect 126 ms 12600 KB Output isn't correct
7 Incorrect 99 ms 12412 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 8912 KB Output isn't correct
2 Incorrect 25 ms 8912 KB Output isn't correct
3 Incorrect 50 ms 9932 KB Output isn't correct
4 Incorrect 46 ms 9940 KB Output isn't correct
5 Incorrect 67 ms 10364 KB Output isn't correct
6 Incorrect 75 ms 11124 KB Output isn't correct
7 Incorrect 87 ms 11212 KB Output isn't correct
8 Incorrect 123 ms 12604 KB Output isn't correct
9 Incorrect 290 ms 18608 KB Output isn't correct
10 Incorrect 178 ms 15168 KB Output isn't correct
11 Incorrect 201 ms 15756 KB Output isn't correct
12 Incorrect 285 ms 17984 KB Output isn't correct
13 Incorrect 264 ms 18784 KB Output isn't correct