Submission #1119581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119581		PieArmy	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	566 ms	46164 KiB

Main

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int arr[200001],better[200001],ans[1000001],idx[200001];

struct Seg{
	int n;
	vector<int>tree;
	void init(int N){
		n=N;
		tree.resize(n<<2,0);
	}
	int l,r;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]=r;
			return;
		}
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		tree[node]=tree[node*2]+tree[node*2+1];
	}
	void update(int tar,int x){
		l=tar;
		r=x;
		up();
	}
	pair<int,int> qu(int node=1,int left=0,int right=-1,int sum=0){
		if(right==-1)right=n-1;
		if(left==right){
			return {idx[left]+l-sum-1,idx[left]};
		}
		if(tree[node*2]>=l-sum)return qu(node*2,left,mid,sum);
		else return qu(node*2+1,mid+1,right,sum+tree[node*2]);
	}
	pair<int,int> query(int x){
		l=x;
		return qu();
	}
}seg;

struct Lazy{
	int n;
	vector<int>lazy,arr;
	void init(int N){
		n=N;
		lazy.resize(n<<2,sonsuz);
		arr.resize(n,0);
		for(int i=0;i<n;i++){
			arr[i]=better[i];
		}
	}
	void push(int node,int left,int right){
		if(lazy[node]==sonsuz)return;
		if(left==right){
			arr[left]=min(arr[left],lazy[node]);
		}
		else{
			lazy[node*2]=min(lazy[node],lazy[node*2]);
			lazy[node*2+1]=min(lazy[node*2+1],lazy[node]-mid+left-1);
		}
		lazy[node]=sonsuz;
	}
	void up(int node,int left,int right,int l,int r,int add){
		if(right==-1)right=n-1;
		if(left>=l&&right<=r){
			push(node,left,right);
			lazy[node]=add;
			return;
		}
		if(left>r||right<l)return;
		if(l<=mid){
			up(node*2,left,mid,l,min(mid,r),add);
			add-=min(mid,r)-l+1;
		}
		if(r>mid){
			up(node*2+1,mid+1,right,max(mid+1,l),r,add);
		}
	}
	void update(int lef,int rig){
		up(1,0,n-1,lef,rig,rig-lef+1);
	}
	int query(int tar){
		int node=1,left=0,right=n-1;
		while(left<right){
			push(node,left,right);
			node*=2;
			if(tar>mid){
				node++;
				left=mid+1;
			}
			else right=mid;
		}
		push(node,left,right);
		return arr[left];
	}
}jump;

int n,q;

void code(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		idx[arr[i]]=i;
	}
	seg.init(n+1);
	for(int i=n;i>=1;i--){
		better[i]=1;
		while(i+better[i]<=n&&arr[i+better[i]]<arr[i])better[i]+=better[i+better[i]];
	}
	jump.init(n+1);
	pair<pair<int,int>,int>Q[q];
	for(int i=0;i<q;i++){
		cin>>Q[i].fr.fr>>Q[i].fr.sc;
		Q[i].sc=i;
	}
	sort(Q,Q+q);
	int loc=0;
	while(loc<q&&Q[loc].fr.fr==0){
		ans[Q[loc].sc]=arr[Q[loc].fr.sc];
		loc++;
	}
	for(int i=1;i<=n;i+=better[i]){
		seg.update(arr[i],better[i]);
	}

	int t=0;
	while(++t){
		{
			pair<int,int>res=seg.query(n/2);
			if(res.fr-res.sc+1==jump.query(res.sc))break;
			seg.update(arr[res.sc],res.fr-res.sc+1);
			int z=jump.query(res.sc);
			for(int i=res.fr+1,j;i-z<res.sc;i+=j){
				j=jump.query(i);
				seg.update(arr[i],j);
			}
			jump.update(res.sc,res.fr);
		}
		while(loc<q&&Q[loc].fr.fr==t){
			ans[Q[loc].sc]=arr[seg.query(Q[loc].fr.sc).fr];
			loc++;
		}
	}
	while(loc<q){
		ans[Q[loc].sc]=arr[seg.query(Q[loc].fr.sc).fr];
		loc++;
	}
	for(int i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
	int t=1;
	if(!t)cin>>t;
	while(t--){code();cout<<endl;}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:168:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:168:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25