oj.uz

Submission #643731

# Submission time Handle Problem Language Result Execution time Memory
643731 2022-09-22T19:44:46 Z kingfran1907 Abracadabra (CEOI22_abracadabra) C++14
25 / 100
 152 ms 28004 KB 
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, q;
int niz[maxn];
int pos[maxn];
int t[maxn], p[maxn];
vector< int > qs[maxn];
int sol[maxn];
int tour[treesiz];
int l[maxn], r[maxn];

void update(int x, int val) {
	x += off;
	tour[x] = val;

	x /= 2;
	while (x > 0) tour[x] = tour[x * 2] + tour[x * 2 + 1], x /= 2;
}

int fin(int l, int r, int node, int val) {
	if (l == r) return l;

	int mid = (l + r) / 2;
	if (tour[node * 2] >= val) return fin(l, mid, node * 2, val);
	return fin(mid + 1, r, node * 2 + 1, val - tour[node * 2]);
}

int query(int a, int b, int l, int r, int node) {
	if (l > b || r < a) return 0;
	if (l >= a && r <= b) return tour[node];

	int mid = (l + r) / 2;
	return query(a, b, l, mid, node * 2) + query(a, b, mid + 1, r, node * 2 + 1);
}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; i++) 
		scanf("%d", niz+i);

	for (int i = 0; i < q; i++) {
		scanf("%d%d", t+i, p+i);
		t[i] = min(t[i], n); p[i]--;
		qs[t[i]].push_back(i);
	}

	niz[n] = inf;
	stack< int > s; s.push(n);
	for (int i = n - 1; i >= 0; i--) {
		while (niz[s.top()] < niz[i]) s.pop();
		pos[i] = s.top();
		s.push(i);
	}

	for (int tren : qs[0]) sol[tren] = niz[p[tren]];
	
	int ptr = 0;
	memset(r, -1, sizeof r);
	while (ptr < n) {
		int val = niz[ptr];
		l[val] = ptr;
		r[val] = pos[ptr] - 1;
		update(val, r[val] - l[val] + 1);
		//printf("block: %d (%d %d)\n", val, l[val], r[val]);

		ptr = pos[ptr];
	}

	update(n + 1, 100);
	for (int ac = 1; ac <= n; ac++) {
		int ind = fin(0, off - 1, 1, n / 2 + 1);
		//printf("ind: %d\n", ind);
		assert(query(1, n, 0, off - 1, 1) == n);
		int prev = query(0, ind - 1, 0, off - 1, 1);
		//printf("middle: %d --> %d\n", ind, prev);
		if (prev != n / 2) {
			int ptr = l[ind] + n / 2 - prev;
			int cp = ptr;
			//printf("ptr: %d\n", ptr);

			while (ptr <= r[ind]) {
				//printf("current ptr: %d\n", ptr);
				int val = niz[ptr];
				l[val] = ptr, r[val] = min(pos[ptr], r[ind] + 1) - 1;
				update(val, r[val] - l[val] + 1);
				//printf("block: %d (%d %d)\n", val, l[val], r[val]);
				ptr = pos[ptr];
			}
			r[ind] = cp - 1;
			update(ind, r[ind] - l[ind] + 1);
			//printf("reduce block: %d --> %d %d\n", ind, l[ind], r[ind]);
		}

		for (int tren : qs[ac]) {
			//printf("answering: %d\n", tren + 1);
			int ind = fin(0, off - 1, 1, p[tren] + 1);
			//assert(ind <= n);
			//printf("in block: %d (%d %d)\n", ind, l[ind], r[ind]);
			//assert(r[ind] - l[ind] >= 0);
			int prev = query(0, ind - 1, 0, off - 1, 1);
			//printf("prev size: %d\n", prev);
			sol[tren] = niz[l[ind] + p[tren] - prev];
		}
	}

	for (int i = 0; i < q; i++) 
		printf("%d\n", sol[i]);
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d", niz+i);
      |   ~~~~~^~~~~~~~~~~~~
Main.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d", t+i, p+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 28004 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 152 ms 24528 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 11416 KB Output is correct
2 Correct 115 ms 12104 KB Output is correct
3 Correct 148 ms 12360 KB Output is correct
4 Correct 97 ms 11516 KB Output is correct
5 Correct 100 ms 11744 KB Output is correct
6 Correct 91 ms 11592 KB Output is correct
7 Correct 104 ms 11316 KB Output is correct
8 Correct 96 ms 11420 KB Output is correct
9 Correct 91 ms 11980 KB Output is correct
10 Correct 81 ms 11392 KB Output is correct
11 Correct 79 ms 10956 KB Output is correct
12 Correct 86 ms 11324 KB Output is correct
13 Correct 81 ms 11324 KB Output is correct
14 Correct 78 ms 11632 KB Output is correct
15 Correct 75 ms 10956 KB Output is correct
16 Correct 38 ms 8012 KB Output is correct
17 Correct 67 ms 10992 KB Output is correct
18 Correct 79 ms 9824 KB Output is correct
19 Correct 3 ms 5844 KB Output is correct
20 Correct 3 ms 5844 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 28004 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -