oj.uz

Submission #725869

# Submission time Handle Problem Language Result Execution time Memory
725869 2023-04-18T08:04:47 Z amunduzbaev Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 46272 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
#define int ll

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q; cin >> n >> q;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin >> a[i]; a[i]--;
	}
	
	vector<int> t(q), id(q);
	vector<int> p(q), res(q);
	for(int i=0;i<q;i++){
		cin >> t[i] >> id[i]; --id[i];
		p[i] = i;
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		if(t[i] != t[j]) return t[i] < t[j];
		else return id[i] < id[j];
	});
	int j = 0;
	while(j < q && t[p[j]] == 0){
		res[p[j]] = a[id[p[j]]];
		j++;
	}
	vector<int> cnt(n), pos(n), par(n, n), ss;
	for(int i=n-1;~i;i--){
		pos[a[i]] = i;
		while(!ss.empty() && a[ss.back()] < a[i]) ss.pop_back();
		if(!ss.empty()) par[i] = ss.back();
		ss.push_back(i);
	}
	{
		int i = 0, m = n / 2;
		while(i < m){
			cnt[a[i]] = min(m, par[i]) - i;
			i = par[i];
		}
		i = m;
		while(i < n){
			cnt[a[i]] = par[i] - i;
			i = par[i];
		}
	}
	
	for(int i=1;i<=n;i++){
		int sum = 0, P = -1, rem = 0;
		for(int k=0;k<n;k++){
			while(j < q && t[p[j]] == i && sum + cnt[k] > id[p[j]]){
				res[p[j]] = a[pos[k] + (id[p[j]] - sum)];
				j++;
			}
			sum += cnt[k];
			if(sum >= n / 2 && P == -1){
				rem = sum - n / 2;
				P = k;
			}
		}
		
		if(!rem){
			break;
		}
		cnt[P] -= rem;
		P = pos[P] + cnt[P];
		int k = P; P += rem;
		while(k < P){
			cnt[a[k]] = min(P, par[k]) - k;
			k = par[k];
		}
	}
	
	sort(p.begin() + j, p.end(), [&](int i, int j){
		return id[i] < id[j];
	});
	int sum = 0;
	for(int k=0;k<n;k++){
		while(j < q && sum + cnt[k] > id[p[j]]){
			res[p[j]] = a[pos[k] + (id[p[j]] - sum)];
			j++;
		}
		sum += cnt[k];
	}
	
	for(int i=0;i<q;i++){
		cout<<++res[i]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 43240 KB Output is correct
2 Correct 427 ms 42904 KB Output is correct
3 Correct 393 ms 41328 KB Output is correct
4 Correct 372 ms 40072 KB Output is correct
5 Correct 417 ms 42440 KB Output is correct
6 Correct 384 ms 40276 KB Output is correct
7 Correct 411 ms 42756 KB Output is correct
8 Correct 370 ms 40608 KB Output is correct
9 Correct 353 ms 40060 KB Output is correct
10 Correct 371 ms 40840 KB Output is correct
11 Correct 371 ms 40680 KB Output is correct
12 Correct 336 ms 39396 KB Output is correct
13 Correct 359 ms 40696 KB Output is correct
14 Correct 381 ms 41604 KB Output is correct
15 Correct 407 ms 41740 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 338 ms 39936 KB Output is correct
18 Correct 340 ms 39640 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 316 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3016 ms 46272 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3022 ms 8320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 43240 KB Output is correct
2 Correct 427 ms 42904 KB Output is correct
3 Correct 393 ms 41328 KB Output is correct
4 Correct 372 ms 40072 KB Output is correct
5 Correct 417 ms 42440 KB Output is correct
6 Correct 384 ms 40276 KB Output is correct
7 Correct 411 ms 42756 KB Output is correct
8 Correct 370 ms 40608 KB Output is correct
9 Correct 353 ms 40060 KB Output is correct
10 Correct 371 ms 40840 KB Output is correct
11 Correct 371 ms 40680 KB Output is correct
12 Correct 336 ms 39396 KB Output is correct
13 Correct 359 ms 40696 KB Output is correct
14 Correct 381 ms 41604 KB Output is correct
15 Correct 407 ms 41740 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 338 ms 39936 KB Output is correct
18 Correct 340 ms 39640 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Execution timed out 3016 ms 46272 KB Time limit exceeded
22 Halted 0 ms 0 KB -