Submission #864781

#	Time	Username	Problem	Language	Result	Execution time	Memory
864781		tolbi	Abracadabra (CEOI22_abracadabra)	C++17	0 / 100	3056 ms	19688 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define tol(bi) (1LL<<((int)(bi)))
struct SegTree{
	vector<int> segtree;
	SegTree(int n){
		segtree.resize(n,0);
	}
	void update(int node, int x){
		segtree[node]=x;
	}
	int query(int l, int r){
		int ans = 0;
		for (int i = l; i <= r; i++){
			ans+=segtree[i];
		}
		return ans;
	}
	int find(int x){
		int crr = 0;
		for (int i = 0; i < segtree.size(); i++){
			crr+=segtree[i];
			if (crr>x) return i;
		}
		assert(false);
		return 23;
	}
};
int main(){
	int n,q;
	cin>>n>>q;
	vector<int> arr(n);
	for (int i = 0; i < n; i++){
		cin>>arr[i];
	}
	vector<int> bendensonra(n,n);
	vector<int> stk;
	vector<int> posses(n+1);
	for (int i = n-1; i >= 0; i--){
		posses[arr[i]]=i;
		while (stk.size() && arr[stk.back()]<arr[i]) stk.pop_back();
		if (stk.size()) bendensonra[i]=stk.back();
		stk.push_back(i);
	}
	vector<array<int,3>> qarr(q);
	for (int i = 0; i < q; ++i)
	{
		cin>>qarr[i][0]>>qarr[i][1];
		qarr[i][2]=i;
	}
	sort(qarr.begin(), qarr.end());
	int time = 0;
	SegTree segtree(n+1);
	int _pp = 0;
	while (_pp<n){
		int nex = bendensonra[_pp];
		segtree.update(arr[_pp],nex-_pp);
		_pp=nex;
	}
	vector<int> ansarr(q);
	for (int i = 0; i < q; i++){
		while (time<min(qarr[i][0],2*n)){
			int ele = segtree.find(n/2);
			int pos = posses[ele]+n/2-segtree.query(0,ele-1);
			if (pos!=posses[ele]){
				segtree.update(ele,pos-posses[ele]);
			}
			while (pos<n && segtree.query(arr[pos],arr[pos])==0){
				int nex = bendensonra[pos];
				segtree.update(arr[pos],nex-pos);
				pos=nex;
			}
			time++;
		}
		int ele = segtree.find((qarr[i][1]-1));
		int pos = posses[ele]+(qarr[i][1]-1)-segtree.query(0,ele-1);
		ansarr[qarr[i][2]]=arr[pos];
	}
	for (int i = 0; i < q; ++i)
	{
		cout<<ansarr[i]<<endl;
	}
}

Compilation message (stderr)

Main.cpp: In member function 'int SegTree::find(int)':
Main.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for (int i = 0; i < segtree.size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~

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