oj.uz

Submission #650881

# Submission time Handle Problem Language Result Execution time Memory
650881 2022-10-15T23:15:06 Z Antekb Abracadabra (CEOI22_abracadabra) C++14
100 / 100
 2805 ms 83484 KB 
#include<bits/stdc++.h>
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
 
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
 
using namespace std;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~~
 
template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
	return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
	os<<"{";
	for(int i=0; i<V.size(); i++){
		if(i)os<<" ";
		os<<V[i];
	}
	os<<"}";
	return os;
}
 
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
 
///~~~~~~~~~~~~~~~~~~~~~~~~~
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
 
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int N=(1<<18), INF=1e9+5, mod=1e9+7;
int val[N], ile[N+N], par[N], siz[N], gdzie[N], dep[N], opt[18][N], naj[N];
vi co[N], sum[N];
void add(int i, int v){
	for(i+=N; i; i>>=1){
		ile[i]+=v;
	}
}
pair<int, int> find(int s){
	int v=1;
	while(v<N){
		if(ile[v+v]<s){
			s-=ile[v+v];
			v=v+v+1;
		}
		else v=v+v;
	}
	return mp(v-N, s);
}
/*void split(int i, int a){
	assert(a!=siz[i]);
	//deb(i, siz[i], a);
	add(val[i], a-siz[i]);
	while(siz[i]>a){
		int j=co[i].back();
		co[i].pp();
		siz[i]-=siz[j];
		add(val[j], siz[j]);
		if(siz[i]<a){
			split(j, a-siz[i]);
			siz[i]+=siz[j];
			co[i].pb(j);
			add(val[j], -siz[j]);
		}
	}
	//add(val[i], siz[i]);
}*/
int ans[int(1e6+5)];
set<int> S;
int roz(int i){
	return (*S.upper_bound(i))-i;
}
void split(int i, int s){
	add(val[i], s-roz(i));
	int t=i+s;
	//deb(i, s, t);
	int k=i+roz(i);
	while(k>t){
		int l=naj[k-t];
		int j;
		if(dep[opt[l][k-(1<<l)]]<=dep[opt[l][t]])j=opt[l][k-(1<<l)];
		else j=opt[l][t];
		add(val[j], roz(j));
		S.insert(j);
		//deb(j);
		k=j;
	}
}
int main(){
	naj[1]=0;
	for(int i=2; i<N; i++)naj[i]=naj[i/2]+1;
	BOOST;
	int n, q;
	cin>>n>>q;
	vi V;
	val[0]=n+5;
	V.pb(0);
	S.insert(n+1);
	for(int i=1; i<=n; i++){
		cin>>val[i];
		gdzie[val[i]]=i;
		while(val[V.back()]<val[i])V.pp();
		par[i]=V.back();
		V.pb(i);
	}
	for(int i=n; i>0; i--){
		siz[i]++;
		siz[par[i]]+=siz[i];
		co[i].pb(i);
		//sum[i].pb(1);
	}
	for(int i=1; i<=n; i++){
		dep[i]=dep[par[i]]+1;
		opt[0][i]=i;
		co[par[i]].pb(i);
		//sum[par[i]].pb(sum[par[i]].back()+siz[i]);
		if(par[i]==0){
			add(val[i], siz[i]);
			S.insert(i);
		}
	}
	for(int k=1; k<18; k++){
		for(int i=1; i<=n; i++){
			if(i+(1<<(k-1))>n)opt[k][i]=opt[k-1][i];
			else{
				if(dep[opt[k-1][i+(1<<(k-1))]]<=dep[opt[k-1][i]])opt[k][i]=opt[k-1][i+(1<<(k-1))];
				else opt[k][i]=opt[k-1][i];
				//assert(opt[k][i]);
			}
			//cerr<<opt[k][i]<<" ";
		}
		//cerr<<"\n";
	}
	//deb(co[6]);
	vector<pair<pii, int> > Q(q);
	for(int qq=0; qq<q; qq++){
		cin>>Q[qq].st.st>>Q[qq].st.nd;
		Q[qq].nd=qq;
	}
	sor(Q);
	int wsk=0;
		for(int i=1; i<=n; i++)cerr<<ile[N+i]<<" ";cerr<<"\n";
	for(int t=0; ;t++){
		assert(ile[1]==n);
		bool b=1;
		while(wsk<q && Q[wsk].st.st==t){
			pii a=find(Q[wsk].st.nd);
			//deb(a, Q[wsk]);
			ans[Q[wsk].nd]=val[gdzie[a.st]+a.nd-1];
			wsk++;
		}
		b=0;
		pii c=find(n/2);
		if(c.nd!=roz(gdzie[c.st]))split(gdzie[c.st], c.nd), b=1;
		//for(int i=1; i<=n; i++)cerr<<ile[N+i]<<" ";cerr<<"\n";
		if(!b){
			while(wsk<q){
				pii a=find(Q[wsk].st.nd);
				deb(a, wsk);
				ans[Q[wsk].nd]=val[gdzie[a.st]+a.nd-1];
				wsk++;
			}
			break;
		}
	}
	for(int i=0; i<q; i++)cout<<ans[i]<<"\n";
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:169:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  169 |   for(int i=1; i<=n; i++)cerr<<ile[N+i]<<" ";cerr<<"\n";
      |   ^~~
Main.cpp:169:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  169 |   for(int i=1; i<=n; i++)cerr<<ile[N+i]<<" ";cerr<<"\n";
      |                                              ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 34252 KB Output is correct
2 Correct 492 ms 34124 KB Output is correct
3 Correct 448 ms 33404 KB Output is correct
4 Correct 463 ms 33180 KB Output is correct
5 Correct 456 ms 34496 KB Output is correct
6 Correct 442 ms 33568 KB Output is correct
7 Correct 471 ms 34524 KB Output is correct
8 Correct 442 ms 33852 KB Output is correct
9 Correct 439 ms 33696 KB Output is correct
10 Correct 441 ms 33952 KB Output is correct
11 Correct 454 ms 33904 KB Output is correct
12 Correct 434 ms 33572 KB Output is correct
13 Correct 455 ms 33996 KB Output is correct
14 Correct 450 ms 34380 KB Output is correct
15 Correct 467 ms 34508 KB Output is correct
16 Correct 11 ms 13940 KB Output is correct
17 Correct 424 ms 33996 KB Output is correct
18 Correct 425 ms 33748 KB Output is correct
19 Correct 8 ms 13780 KB Output is correct
20 Correct 8 ms 13812 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 962 ms 72460 KB Output is correct
2 Correct 886 ms 72764 KB Output is correct
3 Correct 857 ms 66772 KB Output is correct
4 Correct 804 ms 59996 KB Output is correct
5 Correct 838 ms 69184 KB Output is correct
6 Correct 800 ms 68924 KB Output is correct
7 Correct 831 ms 72212 KB Output is correct
8 Correct 811 ms 73036 KB Output is correct
9 Correct 814 ms 68116 KB Output is correct
10 Correct 813 ms 69964 KB Output is correct
11 Correct 815 ms 64356 KB Output is correct
12 Correct 767 ms 63420 KB Output is correct
13 Correct 798 ms 69824 KB Output is correct
14 Correct 787 ms 67924 KB Output is correct
15 Correct 822 ms 73480 KB Output is correct
16 Correct 515 ms 41560 KB Output is correct
17 Correct 829 ms 76900 KB Output is correct
18 Correct 746 ms 60856 KB Output is correct
19 Correct 563 ms 46548 KB Output is correct
20 Correct 2805 ms 53016 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 34676 KB Output is correct
2 Correct 337 ms 34756 KB Output is correct
3 Correct 370 ms 34128 KB Output is correct
4 Correct 304 ms 30124 KB Output is correct
5 Correct 331 ms 32516 KB Output is correct
6 Correct 298 ms 30924 KB Output is correct
7 Correct 326 ms 31728 KB Output is correct
8 Correct 300 ms 31064 KB Output is correct
9 Correct 323 ms 32312 KB Output is correct
10 Correct 292 ms 30272 KB Output is correct
11 Correct 304 ms 30284 KB Output is correct
12 Correct 293 ms 30200 KB Output is correct
13 Correct 289 ms 30408 KB Output is correct
14 Correct 312 ms 30972 KB Output is correct
15 Correct 298 ms 30140 KB Output is correct
16 Correct 266 ms 27644 KB Output is correct
17 Correct 306 ms 34248 KB Output is correct
18 Correct 295 ms 29448 KB Output is correct
19 Correct 8 ms 13780 KB Output is correct
20 Correct 8 ms 13780 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 34252 KB Output is correct
2 Correct 492 ms 34124 KB Output is correct
3 Correct 448 ms 33404 KB Output is correct
4 Correct 463 ms 33180 KB Output is correct
5 Correct 456 ms 34496 KB Output is correct
6 Correct 442 ms 33568 KB Output is correct
7 Correct 471 ms 34524 KB Output is correct
8 Correct 442 ms 33852 KB Output is correct
9 Correct 439 ms 33696 KB Output is correct
10 Correct 441 ms 33952 KB Output is correct
11 Correct 454 ms 33904 KB Output is correct
12 Correct 434 ms 33572 KB Output is correct
13 Correct 455 ms 33996 KB Output is correct
14 Correct 450 ms 34380 KB Output is correct
15 Correct 467 ms 34508 KB Output is correct
16 Correct 11 ms 13940 KB Output is correct
17 Correct 424 ms 33996 KB Output is correct
18 Correct 425 ms 33748 KB Output is correct
19 Correct 8 ms 13780 KB Output is correct
20 Correct 8 ms 13812 KB Output is correct
21 Correct 962 ms 72460 KB Output is correct
22 Correct 886 ms 72764 KB Output is correct
23 Correct 857 ms 66772 KB Output is correct
24 Correct 804 ms 59996 KB Output is correct
25 Correct 838 ms 69184 KB Output is correct
26 Correct 800 ms 68924 KB Output is correct
27 Correct 831 ms 72212 KB Output is correct
28 Correct 811 ms 73036 KB Output is correct
29 Correct 814 ms 68116 KB Output is correct
30 Correct 813 ms 69964 KB Output is correct
31 Correct 815 ms 64356 KB Output is correct
32 Correct 767 ms 63420 KB Output is correct
33 Correct 798 ms 69824 KB Output is correct
34 Correct 787 ms 67924 KB Output is correct
35 Correct 822 ms 73480 KB Output is correct
36 Correct 515 ms 41560 KB Output is correct
37 Correct 829 ms 76900 KB Output is correct
38 Correct 746 ms 60856 KB Output is correct
39 Correct 563 ms 46548 KB Output is correct
40 Correct 2805 ms 53016 KB Output is correct
41 Correct 374 ms 34676 KB Output is correct
42 Correct 337 ms 34756 KB Output is correct
43 Correct 370 ms 34128 KB Output is correct
44 Correct 304 ms 30124 KB Output is correct
45 Correct 331 ms 32516 KB Output is correct
46 Correct 298 ms 30924 KB Output is correct
47 Correct 326 ms 31728 KB Output is correct
48 Correct 300 ms 31064 KB Output is correct
49 Correct 323 ms 32312 KB Output is correct
50 Correct 292 ms 30272 KB Output is correct
51 Correct 304 ms 30284 KB Output is correct
52 Correct 293 ms 30200 KB Output is correct
53 Correct 289 ms 30408 KB Output is correct
54 Correct 312 ms 30972 KB Output is correct
55 Correct 298 ms 30140 KB Output is correct
56 Correct 266 ms 27644 KB Output is correct
57 Correct 306 ms 34248 KB Output is correct
58 Correct 295 ms 29448 KB Output is correct
59 Correct 8 ms 13780 KB Output is correct
60 Correct 8 ms 13780 KB Output is correct
61 Correct 1241 ms 82668 KB Output is correct
62 Correct 1150 ms 83484 KB Output is correct
63 Correct 1136 ms 79320 KB Output is correct
64 Correct 1010 ms 72820 KB Output is correct
65 Correct 1072 ms 76144 KB Output is correct
66 Correct 992 ms 72908 KB Output is correct
67 Correct 1031 ms 73812 KB Output is correct
68 Correct 995 ms 72856 KB Output is correct
69 Correct 1041 ms 73080 KB Output is correct
70 Correct 1018 ms 71104 KB Output is correct
71 Correct 995 ms 71108 KB Output is correct
72 Correct 977 ms 69256 KB Output is correct
73 Correct 986 ms 69452 KB Output is correct
74 Correct 1002 ms 71752 KB Output is correct
75 Correct 998 ms 70276 KB Output is correct
76 Correct 493 ms 41064 KB Output is correct
77 Correct 977 ms 76128 KB Output is correct
78 Correct 946 ms 67100 KB Output is correct
79 Correct 8 ms 13780 KB Output is correct
80 Correct 8 ms 13864 KB Output is correct