oj.uz

Submission #536721

# Submission time Handle Problem Language Result Execution time Memory
536721 2022-03-14T00:29:51 Z LucaDantas Cake (CEOI14_cake) C++17
0 / 100
 274 ms 25076 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;

	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 8128 KB Output is correct
2 Incorrect 6 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 213 ms 20556 KB Output isn't correct
2 Correct 181 ms 20640 KB Output is correct
3 Incorrect 226 ms 20556 KB Output isn't correct
4 Correct 190 ms 20680 KB Output is correct
5 Incorrect 211 ms 20996 KB Output isn't correct
6 Incorrect 230 ms 21416 KB Output isn't correct
7 Incorrect 207 ms 21276 KB Output isn't correct
8 Correct 199 ms 21324 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 12100 KB Output isn't correct
2 Incorrect 50 ms 11968 KB Output isn't correct
3 Incorrect 54 ms 11940 KB Output isn't correct
4 Incorrect 5 ms 8116 KB Output isn't correct
5 Incorrect 120 ms 15072 KB Output isn't correct
6 Incorrect 114 ms 15052 KB Output isn't correct
7 Incorrect 77 ms 14864 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 9428 KB Output isn't correct
2 Incorrect 26 ms 9344 KB Output isn't correct
3 Incorrect 45 ms 10816 KB Output isn't correct
4 Incorrect 46 ms 10880 KB Output isn't correct
5 Incorrect 64 ms 11452 KB Output isn't correct
6 Incorrect 78 ms 12888 KB Output isn't correct
7 Incorrect 84 ms 12696 KB Output isn't correct
8 Incorrect 131 ms 15072 KB Output isn't correct
9 Incorrect 274 ms 24944 KB Output isn't correct
10 Incorrect 204 ms 18956 KB Output isn't correct
11 Incorrect 197 ms 20000 KB Output isn't correct
12 Incorrect 267 ms 23984 KB Output isn't correct
13 Incorrect 272 ms 25076 KB Output isn't correct