Submission #643712

#	Time	Username	Problem	Language	Result	Execution time	Memory
643712		kingfran1907	Abracadabra (CEOI22_abracadabra)	C++14	0 / 100	140 ms	28020 KiB

Main

#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(tour[1] > n / 2 + 1);
		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] = pos[ptr] - 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);
		}

		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 (stderr)

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
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25