oj.uz

Submission #796394

# Submission time Handle Problem Language Result Execution time Memory
796394 2023-07-28T11:06:27 Z amirhoseinfar1385 Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 304 ms 35924 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;
int kaf=(1<<19),inf=maxn*2;
struct segment{
	int mina[(1<<20)];
	segment(){
		for(int i=0;i<(1<<20);i++){
			mina[i]=inf;
		}
	}
	void upd(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			mina[i]=min(mina[i],w);
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		return ;
	}
	int pors(int i){
		if(i==0){
			return inf;
		}
		int ret=min(mina[i],pors((i>>1)));
		return ret;
	}
}seg;

void solve(int v){
	st.clear();
	st.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]);
		int pp=seg.pors(kaf+link[i]);
		x=min(x,link[i]+pp);
		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;
			v-=f;
			ted-=z;
			seg.upd(1,0,kaf-1,link[i],x-1,ft);
		}
		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";
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 22648 KB Output is correct
2 Correct 244 ms 35924 KB Output is correct
3 Correct 226 ms 31432 KB Output is correct
4 Correct 242 ms 31564 KB Output is correct
5 Correct 257 ms 32204 KB Output is correct
6 Correct 246 ms 31148 KB Output is correct
7 Incorrect 304 ms 35772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 20640 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 6 ms 8916 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -