Submission #636666

#	Time	Username	Problem	Language	Result	Execution time	Memory
636666		MilosMilutinovic	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	1163 ms	248112 KiB

Main

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
 
#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif
 
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
 
clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
 
const int N = 200200;
const int Q = 1000100;
int n, q;
int a[N];
int pos[N];
vector<pair<int, int>> Qs[N];
int ANS[Q];
int r[N];
set<int> setik;
set<int> set_pos;
 
struct Node {
	int l, r, sum;
 
	Node() : sum(0) {}
	Node(int _l, int _r, int _sum) : l(_l), r(_r), sum(_sum) {}
};
const int M = (1 << 22);
Node tree[4 * M + 5];
 
Node merge(Node L, Node R) {
	return Node(L.l, R.r, L.sum + R.sum);
}
void build(int v, int l, int r) {
	tree[v] = Node(l, r, 0);
	if (l == r) return;
	int mid = l + r >> 1;
	build(v * 2, l, mid);
	build(v * 2 + 1, mid + 1, r);
}
void update(int p, int i, int v) {
	if (tree[p].l > i || tree[p].r < i) return;
	if (tree[p].l == tree[p].r) {
		tree[p].sum += v;
		return;
	}
	update(p * 2, i, v);
	update(p * 2 + 1, i, v);
	tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
}
int getPos(int p, int v) {
//	eprintf("segtree: %d %d %d\n", tree[p].l, tree[p].r, v);
	if (tree[p].l == tree[p].r) return tree[p].l;
	if (tree[p * 2].sum < v)
		return getPos(p * 2 + 1, v - tree[p * 2].sum);
	else
		return getPos(p * 2, v);
}
int getSum(int p, int r) {
	if (tree[p].r <= r) return tree[p].sum;
	if (tree[p].l > r) return 0;
	return getSum(p * 2, r) + getSum(p * 2 + 1, r);
}
 
void add(int x, int l) {
//	eprintf("adding %d %d\n", x, l);
	setik.insert(x);	
	set_pos.insert(pos[x]);
	update(1, x, l);
}
void go(int i) {
	i = pos[i];
//	eprintf("OMFG GO FROM %d\n", i);
	while(i <= n && setik.find(a[i]) == setik.end()) {
		int nxt = r[i];
		auto it = set_pos.lower_bound(i);
		if (it != set_pos.end() && *it >= i)
			nxt = min(nxt, *it);
		add(a[i], nxt - i);
		i = nxt;
	}
}
int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
 
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		pos[a[i]] = i;
	}
	vector<int> stk(1, n + 1);
	for (int i = n; i >= 1; i--) {
		while(stk.size() > 1 && a[stk.back()] <= a[i])
			stk.pop_back();
		r[i] = stk.back();
		stk.push_back(i);
	}
	build(1, 0, M - 1);
	go(a[1]);
	for (int i = 0; i < q; i++) {
		int t, x;
		scanf("%d%d", &t, &x);
		Qs[min(t, n)].push_back(mp(x, i));
	}
	for (int i = 0; i <= n; i++) {
		for (auto& p : Qs[i]) {
			int el = getPos(1, p.first);
//			eprintf("p.first = %d el = %d\n", p.first, el);
//			if (p.first == 5)
//				eprintf("hIIIIIII sz = %d\n", setik.size());
			ANS[p.second] = a[pos[el] + p.first - getSum(1, el - 1) - 1];
			assert(ANS[p.second] <= el);
		}
		int id = getPos(1, n / 2 + 1);
//		eprintf("ID = %d\n", id);
		if (getSum(1, id - 1) == n / 2)
			continue;
		int el = a[pos[id] + n / 2 - getSum(1, id - 1)];
		int new_v = n / 2 - getSum(1, id - 1) - (getSum(1, id) - getSum(1, id - 1));
//		eprintf("WTF %d %d and %d\n", id, new_v, el);
		update(1, id, new_v);
		go(el);
	}
	for (int i = 0; i < q; i++)
		printf("%d\n", ANS[i]);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:80:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |  int mid = l + r >> 1;
      |            ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:132:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
Main.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |   scanf("%d%d", &t, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25