oj.uz

답안 #864780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
864780 2023-10-23T15:19:14 Z tolbi Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 1841 ms 40272 KB 
#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;
	}
};
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);
			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

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()){
      |          ~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1610 ms 27436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1841 ms 40272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 218 ms 6232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1610 ms 27436 KB Output isn't correct
2 Halted 0 ms 0 KB -