Submission #789380

#	Time	Username	Problem	Language	Result	Execution time	Memory
789380		ymm	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	660 ms	70804 KiB

Main

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

vector<int> shf(vector<int> vec)
{
	int n = vec.size();
	vector<int> ans;
	int p0 = 0, p1 = n/2;
	Loop (_,0,n) {
		if (p1 == n || (p0 < n/2 && vec[p0] < vec[p1]))
			ans.push_back(vec[p0++]);
		else
			ans.push_back(vec[p1++]);
	}
	return ans;
}

const int N = 1'000'010;
void shf2(int *a, int n)
{
	static int tmp[N];
	int p = n/2;
	while (p < n && a[p] < a[0])
		++p;
	memcpy(tmp, a+n/2, (p-n/2)*sizeof(*a));
	memmove(a+p-n/2, a, (n/2)*sizeof(*a));
	memcpy(a, tmp, (p-n/2)*sizeof(*a));
}

int ans[N];
vector<pii> Q[N];

int *ptr[N];

namespace fen {
	const int lg = 21;
	int a[1<<lg];
	void add(int i, int x) {
		++i;
		while (i < (1<<lg)) {
			a[i] += x;
			i += i&-i;
		}
	}
	int get(int r) {
		int ans = 0;
		while (r > 0) {
			ans += a[r];
			r -= r&-r;
		}
		return ans;
	}
	int get(int l, int r) { return get(r) - get(l); }
	pii bin(int x) {
		int ans = 0;
		int sum = 0;
		LoopR (i,0,lg) {
			if (sum + a[ans + (1<<i)] <= x) {
				sum += a[ans + (1<<i)];
				ans += (1<<i);
			}
		}
		return {ans, sum};
	}
}

int sz[N];
int nxt[N];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	vector<int> vec(n);
	//iota(vec.begin(), vec.end(), 0);
	//auto pleh = vec;
	//int cntt = 0;
	//for (;;) {
	//	int cnt = 0;
	//	vec = pleh;
	//	for (;;) {
	//		auto tmp = shf(vec);
	//		if (tmp == vec)
	//			break;
	//		vec = tmp;
	//		++cnt;
	//	}
	//	cntt = max(cntt, cnt);
	//	if (!next_permutation(pleh.begin(), pleh.end()))
	//		break;
	//}
	//cout << cntt << '\n';
	//return 0;
	//mt19937_64 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
	//iota(vec.begin(), vec.end(), 0);
	//shuffle(vec.begin(), vec.end(), rd);
	for (int &x : vec)
		cin >> x;
	Loop (i,0,q) {
		int t, p;
		cin >> t >> p;
		--p;
		t = min(t, n);
		Q[t].push_back({p, i});
	}
	for (auto [p, j] : Q[0])
		ans[j] = vec[p];
	int mx = -1;
	Loop (i,0,n/2) {
		if (vec[i] > mx) {
			mx = vec[i];
			ptr[mx] = &vec[i];
		}
		sz[mx]++;
	}
	mx = -1;
	Loop (i,n/2,n) {
		if (vec[i] > mx) {
			mx = vec[i];
			ptr[mx] = &vec[i];
		}
		sz[mx]++;
	}
	vector<int> st;
	LoopR (i,0,n) {
		while (st.size() && vec[st.back()] < vec[i])
			st.pop_back();
		if (!st.size())
			nxt[i] = N;
		else
			nxt[i] = st.back() - i;
		st.push_back(i);
	}
	Loop (i,0,N)
		fen::add(i, sz[i]);

	//vecs.push_back(vec);
	Loop (i,0,n) {
		for (auto [p, j] : Q[i+1]) {
			auto [y, beforey] = fen::bin(p);
			//cerr << y << ' ' << beforey << '\n';
			ans[j] = ptr[y][p - beforey];
		}
		auto [x, before] = fen::bin(n/2);
		if (before == n/2)
			continue;
		int cnt = (before + sz[x]) - n/2;
		//cerr << x << " to rem " << cnt << ' ' << sz[x] << '\n';
		sz[x] -= cnt;
		fen::add(x, -cnt);
		int *p = ptr[x] + sz[x];
		//cerr << "first to split is " << *p << '\n';
		int j = 0;
		int rj = p - vec.data();
		while (j < cnt) {
			int g = min(cnt-j, nxt[rj]);
			//cerr << p[j] << " added!\n";
			sz[p[j]] += g;
			fen::add(p[j], g);
			ptr[p[j]] = p+j;
			j += g;
			rj += g;
		}
		//cerr << "hola!\n";
	}
	Loop (i,0,q)
		cout << ans[i] << '\n';
}

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