oj.uz

Submission #789378

# Submission time Handle Problem Language Result Execution time Memory
789378 2023-07-21T10:01:03 Z ymm Abracadabra (CEOI22_abracadabra) C++17
25 / 100
 210 ms 37808 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 < (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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 137 ms 32588 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 210 ms 37808 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 53 ms 10828 KB Output is correct
2 Correct 50 ms 10672 KB Output is correct
3 Correct 61 ms 10564 KB Output is correct
4 Correct 42 ms 10036 KB Output is correct
5 Correct 51 ms 10400 KB Output is correct
6 Correct 44 ms 10012 KB Output is correct
7 Correct 47 ms 10308 KB Output is correct
8 Correct 45 ms 10048 KB Output is correct
9 Correct 47 ms 10168 KB Output is correct
10 Correct 48 ms 9792 KB Output is correct
11 Correct 40 ms 10108 KB Output is correct
12 Correct 45 ms 9896 KB Output is correct
13 Correct 55 ms 9924 KB Output is correct
14 Correct 44 ms 10204 KB Output is correct
15 Correct 56 ms 9952 KB Output is correct
16 Correct 21 ms 7988 KB Output is correct
17 Correct 32 ms 10508 KB Output is correct
18 Correct 42 ms 8608 KB Output is correct
19 Correct 6 ms 5928 KB Output is correct
20 Correct 6 ms 5844 KB Output is correct

Subtask #4
0 / 25.0

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