oj.uz

Submission #537324

# Submission time Handle Problem Language Result Execution time Memory
537324 2022-03-15T01:42:02 Z LucaDantas Cake (CEOI14_cake) C++17
100 / 100
 868 ms 18524 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 2e6+10, logn = 22;

int a[maxn];

struct Query { int x, e; } qr[maxn];

set<pair<int,int>, greater<pair<int,int>>> st;

int main() {
	int n, start; scanf("%d %d", &n, &start);
	for(int i = 1; i <= n; i++)
		scanf("%d", a+i), st.insert({a[i], 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);
		} else {
			int x; scanf("%d", &x);
			qr[i] = {x, -1};
		}
	}
	
	vector<int> l, r; // salvo os dois paretos

	for(int i = start+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 = start-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 == start) puts("0");
			else if(x > start) {
				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 {
			auto [x, pos] = qr[i];
			int val = st.begin()->first+1;
			
			vector<pair<int,int>> add;
			for(int k = 1; k < pos; k++) {
				int id = st.begin()->second;
				st.erase(st.begin());
				val = a[id];
				++a[id];
				add.push_back({a[id], id});
			}
			
			for(auto p : add)
				st.insert(p);
 
			assert(st.find({a[x], x}) != st.end());
			st.erase({a[x], x});
			a[x] = val;
			st.insert({a[x], x});

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

			vector<int> sv;
			while(r.size() && (x > start ? r.back() > x : r.back() < x))
				sv.push_back(r.back()), r.pop_back();

			sv.push_back(x);
			reverse(sv.begin(), sv.end());

			for(int x : sv)
				if(!r.size() || a[x] > a[r.back()])
					r.push_back(x);

			if(x < start) swap(l, r);
		}
	}
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:13:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  int n, start; scanf("%d %d", &n, &start);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~
cake.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d", a+i), st.insert({a[i], i});
      |   ~~~~~^~~~~~~~~~~
cake.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
cake.cpp:19:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   char c; scanf(" %c", &c);
      |           ~~~~~^~~~~~~~~~~
cake.cpp:21:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |    scanf("%d %d", &qr[i].x, &qr[i].e);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:23:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 12 ms 896 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 4564 KB Output is correct
2 Correct 291 ms 4724 KB Output is correct
3 Correct 388 ms 4720 KB Output is correct
4 Correct 246 ms 4668 KB Output is correct
5 Correct 487 ms 5464 KB Output is correct
6 Correct 465 ms 5484 KB Output is correct
7 Correct 388 ms 5500 KB Output is correct
8 Correct 389 ms 5484 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 6732 KB Output is correct
2 Correct 67 ms 6584 KB Output is correct
3 Correct 53 ms 6580 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 245 ms 14464 KB Output is correct
6 Correct 215 ms 14388 KB Output is correct
7 Correct 99 ms 14184 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 932 KB Output is correct
2 Correct 38 ms 992 KB Output is correct
3 Correct 72 ms 3556 KB Output is correct
4 Correct 82 ms 3532 KB Output is correct
5 Correct 125 ms 1816 KB Output is correct
6 Correct 145 ms 5200 KB Output is correct
7 Correct 147 ms 2764 KB Output is correct
8 Correct 227 ms 6864 KB Output is correct
9 Correct 868 ms 18492 KB Output is correct
10 Correct 426 ms 5416 KB Output is correct
11 Correct 491 ms 6484 KB Output is correct
12 Correct 735 ms 15944 KB Output is correct
13 Correct 639 ms 18524 KB Output is correct