oj.uz

Submission #789375

# Submission time Handle Problem Language Result Execution time Memory
789375 2023-07-21T09:59:19 Z ymm Abracadabra (CEOI22_abracadabra) C++17
25 / 100
 207 ms 33452 KB 
#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 = 200'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 = 18;
	int a[1<<lg];
	void add(int i, int x) {
		++i;
		while (i < N) {
			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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 126 ms 33452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 207 ms 32608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11648 KB Output is correct
2 Correct 50 ms 12344 KB Output is correct
3 Correct 50 ms 12288 KB Output is correct
4 Correct 44 ms 11536 KB Output is correct
5 Correct 52 ms 12136 KB Output is correct
6 Correct 45 ms 11524 KB Output is correct
7 Correct 53 ms 12048 KB Output is correct
8 Correct 47 ms 11596 KB Output is correct
9 Correct 49 ms 11904 KB Output is correct
10 Correct 50 ms 11300 KB Output is correct
11 Correct 42 ms 11564 KB Output is correct
12 Correct 40 ms 11304 KB Output is correct
13 Correct 54 ms 11224 KB Output is correct
14 Correct 42 ms 11552 KB Output is correct
15 Correct 44 ms 11084 KB Output is correct
16 Correct 18 ms 8232 KB Output is correct
17 Correct 35 ms 11552 KB Output is correct
18 Correct 38 ms 9676 KB Output is correct
19 Correct 7 ms 5716 KB Output is correct
20 Correct 7 ms 5800 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 126 ms 33452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -