Submission #636665

#	Time	Username	Problem	Language	Result	Execution time	Memory
636665		MilosMilutinovic	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	2894 ms	61372 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;

const int M = (1 << 22);
int tree[8 * M + 5];

void update(int p, int l, int r, int i, int v) {
	if (l == r) {
		assert(l == i);
		tree[p] = v;
		return;
	}
	int mid = l + r >> 1;
	if (i <= mid)
		update(p * 2, l, mid, i, v);
	else
		update(p * 2 + 1, mid + 1, r, i, v);
	tree[p] = tree[p * 2] + tree[p * 2 + 1];
}
int getSum(int p, int l, int r, int ql, int qr) {
	if (l > r || l > qr || r < ql) return 0;
	if (ql <= l && r <= qr) return tree[p];
	int mid = l + r >> 1;
	return getSum(p * 2, l, mid, ql, qr) + getSum(p * 2 + 1, mid + 1, r, ql, qr);
}
int getSum(int p, int r) {
	return getSum(p, 0, M - 1, 0, r);
}
int getPos(int p, int v) {
//	eprintf("segtree: %d %d %d\n", tree[p].l, tree[p].r, v);
	int l = 0, r = M - 1, at = -1;
	while (l <= r) {
		int mid = l + r >> 1;
		if (getSum(1, mid) < v)
			at = mid, l = mid + 1;
		else
			r = mid - 1;
	}
	return at + 1;
}

void add(int x, int l) {
//	eprintf("adding %d %d\n", x, l);
	assert(setik.find(x) == setik.end());
	setik.insert(x);
	set_pos.insert(pos[x]);
	update(1, 0, M - 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);
	}
	go(a[1]);
	for (int i = 0; i < q; i++) {
		int t, x;
		scanf("%d%d", &t, &x);
		Qs[min(t, n + 1)].push_back(mp(x, i));
	}
	for (int i = 0; i <= n + 1; 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());
			assert(getSum(1, el) >= p.first);
			assert(getSum(1, el - 1) < p.first);
			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);
		assert(getSum(1, id) > n / 2);
//		eprintf("ID = %d\n", id);
		assert(getSum(1, id - 1) <= n / 2);
		if (setik.size() == n)
			continue;
		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);
//		eprintf("WTF %d %d and %d\n", id, new_v, el);
		update(1, 0, M - 1, id, new_v);
		assert(setik.find(el) == setik.end());
		go(el);
	}
	for (int i = 0; i < q; i++)
		printf("%d\n", ANS[i]);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void update(int, int, int, int, int)':
Main.cpp:74:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |  int mid = l + r >> 1;
      |            ~~^~~
Main.cpp: In function 'int getSum(int, int, int, int, int)':
Main.cpp:84:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |  int mid = l + r >> 1;
      |            ~~^~~
Main.cpp: In function 'int getPos(int, int)':
Main.cpp:94:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:161:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  161 |   if (setik.size() == n)
      |       ~~~~~~~~~~~~~^~~~
Main.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
Main.cpp:143:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |   scanf("%d%d", &t, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~

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