oj.uz

Submission #796741

# Submission time Handle Problem Language Result Execution time Memory
796741 2023-07-28T16:40:39 Z amirhoseinfar1385 Abracadabra (CEOI22_abracadabra) C++17
40 / 100
 311 ms 33504 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int n,q;
int all[maxn],res[maxn],link[maxn];
set<int>st,salam;
void solve(int v){
	st.clear();
	st.insert(n+1);
	salam.clear();
	salam.insert(n+1);
	for(int i=1;i<=n;i++){
		link[all[i]]=i;
	}
	int now=n;
	int ted=n/2;
	for(int i=n;i>=1;i--){
		//<<i<<endl;
		auto x=*st.lower_bound(link[i]);
		auto y=*salam.upper_bound(link[i]);
		x=min(x,y);
		if(x==link[i])
		{
			continue;
		}
		int len=x-link[i];
		int z=0,ft=ted;
		if(ted>0){
			int f=min((len-1)/ted,v);
			z=len-f*ted;
			for(int j=link[i]+len-ted;j>link[i]+z-1;j-=ted){
				salam.insert(j);
			}
			v-=f;
			ted-=z;
		}
		else{
			z=len;
		}
		//cout<<len<<" "<<ted<<" "<<z<<" "<<i<<" "<<link[i]<<" "<<x<<"\n";
		//<<len<<" "<<ted<<" "<<z<<endl; 
		for(int j=z-1;j>=0;j--){
			//<<j<<" "<<link[i]<<" "<<all[link[i]+j]<<" "<<len<<" "<<now<<endl;
			res[now]=all[link[i]+j];
			st.insert(link[i]+j);
			now--;
			//<<"salam"<<endl;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	//freopen("out2.txt","w",stdout);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	int u,v;
	cin>>v>>u;
	solve(v);
	int lastv=v;
	cout<<res[u]<<"\n";
	for(int i=1;i<q;i++){
		cin>>v>>u;
		if(lastv!=v){
			assert(0);
			solve(v);
			lastv=v;
		}
		cout<<res[u]<<"\n";
	}
}

Compilation message

Main.cpp: In function 'void solve(int)':
Main.cpp:27:11: warning: unused variable 'ft' [-Wunused-variable]
   27 |   int z=0,ft=ted;
      |           ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 25732 KB Output is correct
2 Correct 248 ms 33504 KB Output is correct
3 Correct 266 ms 29636 KB Output is correct
4 Correct 270 ms 29224 KB Output is correct
5 Correct 273 ms 30560 KB Output is correct
6 Correct 268 ms 28256 KB Output is correct
7 Correct 311 ms 32460 KB Output is correct
8 Correct 287 ms 31044 KB Output is correct
9 Correct 262 ms 29108 KB Output is correct
10 Correct 311 ms 29516 KB Output is correct
11 Correct 229 ms 26308 KB Output is correct
12 Correct 235 ms 26528 KB Output is correct
13 Correct 251 ms 28668 KB Output is correct
14 Correct 233 ms 27340 KB Output is correct
15 Correct 274 ms 30280 KB Output is correct
16 Correct 86 ms 13112 KB Output is correct
17 Correct 219 ms 26888 KB Output is correct
18 Correct 177 ms 24092 KB Output is correct
19 Correct 124 ms 15852 KB Output is correct
20 Correct 145 ms 17176 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 17980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -