oj.uz

Submission #537312

# Submission time Handle Problem Language Result Execution time Memory
537312 2022-03-15T00:43:40 Z LucaDantas Cake (CEOI14_cake) C++17
0 / 100
 937 ms 22732 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>> 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 {
			// upd
			auto [x, e] = qr[i];

			st.erase({a[x], x});

			vector<pair<int,int>> add;

			if(e == 1) a[x] = st.rbegin()->first+1;
			else for(int k = 1; k < e; k++) {
				auto p = *st.rbegin();
				st.erase(p);
				a[x] = p.first;
				p.first++;
				a[p.second]++;
				add.push_back(p);
			}
			for(auto p : add)
				st.insert(p);

			st.insert({a[x], x});

			if(x < start) swap(l, r);
			
			vector<int> sv = {x};
			while(r.size() && (x > start ? 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 < 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 1 ms 212 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 542 ms 6776 KB Output isn't correct
2 Correct 308 ms 6872 KB Output is correct
3 Incorrect 390 ms 6920 KB Output isn't correct
4 Correct 212 ms 6716 KB Output is correct
5 Incorrect 614 ms 7824 KB Output isn't correct
6 Incorrect 539 ms 8148 KB Output isn't correct
7 Incorrect 397 ms 8052 KB Output isn't correct
8 Correct 275 ms 8280 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 7316 KB Output isn't correct
2 Incorrect 56 ms 7188 KB Output isn't correct
3 Incorrect 56 ms 7144 KB Output isn't correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 228 ms 15036 KB Output isn't correct
6 Incorrect 229 ms 15052 KB Output isn't correct
7 Incorrect 107 ms 14820 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 1300 KB Output isn't correct
2 Incorrect 33 ms 1424 KB Output isn't correct
3 Incorrect 75 ms 4136 KB Output isn't correct
4 Incorrect 100 ms 4168 KB Output isn't correct
5 Incorrect 135 ms 2480 KB Output isn't correct
6 Incorrect 137 ms 5772 KB Output isn't correct
7 Incorrect 136 ms 3340 KB Output isn't correct
8 Incorrect 243 ms 7452 KB Output isn't correct
9 Incorrect 937 ms 22608 KB Output isn't correct
10 Incorrect 429 ms 6804 KB Output isn't correct
11 Incorrect 550 ms 8544 KB Output isn't correct
12 Incorrect 921 ms 19744 KB Output isn't correct
13 Incorrect 727 ms 22732 KB Output isn't correct