Submission #864794

#	Time	Username	Problem	Language	Result	Execution time	Memory
864794		tolbi	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	1981 ms	41216 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(tol(ceil(log2(n)+1))-1,0);
	}
	void update(int node, int x){
		node+=segtree.size()/2;
		segtree[node]=x;
		while (node){
			node=(node-1)/2;
			segtree[node]=segtree[node*2+1]+segtree[node*2+2];
		}
	}
	int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		if (l>=tarl && r<=tarr) return segtree[node];
		if (l>tarr || r<tarl) return 0;
		int mid = l+(r-l)/2;
		int lnode = query(tarl, tarr, l, mid, node*2+1);
		int rnode = query(tarl, tarr, mid+1, r, node*2+2);
		return lnode+rnode;
	}
	int find(int x){
		int node = 0;
		while (node*2+1<segtree.size()){
			if (segtree[node*2+1]<=x){
				x-=segtree[node*2+1];
				node=node*2+2;
			}
			else {
				node=node*2+1;
			}
		}
		return node-segtree.size()/2;
	}
	void debug(){
		for (int i = segtree.size()/2; i < segtree.size(); i++){
			cout<<segtree[i]<<" ";
		}
		cout<<endl;
	}
};
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],n)){
			int ele = segtree.find(n/2);
			int pos = posses[ele]+n/2-segtree.query(0,ele-1);
			int bound = posses[ele]+segtree.query(ele,ele);
			if (pos!=posses[ele]){
				segtree.update(ele,pos-posses[ele]);
			}
			while (pos<bound && segtree.query(arr[pos],arr[pos])==0){
				int nex = bendensonra[pos];
				segtree.update(arr[pos],min(bound,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;
	}
}
//3 1 5 4 2 6

Compilation message (stderr)

Main.cpp: In member function 'int SegTree::find(int)':
Main.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   while (node*2+1<segtree.size()){
      |          ~~~~~~~~^~~~~~~~~~~~~~~
Main.cpp: In member function 'void SegTree::debug()':
Main.cpp:40:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for (int i = segtree.size()/2; i < segtree.size(); i++){
      |                                  ~~^~~~~~~~~~~~~~~~

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