Submission #198077

#	Time	Username	Problem	Language	Result	Execution time	Memory
198077		dndhk	Editor (BOI15_edi)	C++14	100 / 100	262 ms	60380 KiB

edi

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int MAX_N = 300000;
const int MAX_K = 20;

typedef pair<int, int> pii;

vector<pii> vt;
int prv[MAX_N+1];
int N;
vector<pii> v;

int num[MAX_N+1];
int chk[MAX_N+1];

priority_queue<int> pq1, pq2;

vector<int> vc;
int cnt[MAX_N+1];
pii frt[MAX_N+1][MAX_K+1];

void make_prv(){
	for(int i=0; i<N; i++){
		if(vt[i].first==1){
			for(int j=0; j<MAX_K; j++){
				frt[i][j] = {i, 0};
			}
		}else{
			int n = i;
			for(int j=MAX_K-1; j>=0; j--){
				//cout<<n<<" "<<j<<" "<<frt[n-1][j].second<<" "<<vt[i].second<<endl;
				if(frt[n-1][j].second>=vt[i].second){
					n = frt[n-1][j].first;
				}
			}
			prv[i] = n-1;
			//cout<<i<<" "<<prv[i]<<endl;
			frt[i][0] = {prv[i], vt[i].second};
			//cout<<frt[i][0].first<<" "<<frt[i][0].second<<endl;
			for(int j=1; j<MAX_K; j++){
				if(frt[i][j-1].first==0){
					frt[i][j] = {0, 0};
				}else{
					frt[i][j].first = frt[frt[i][j-1].first-1][j-1].first;
					frt[i][j].second = min(frt[i][j-1].second, frt[frt[i][j-1].first-1][j-1].second);
				}
				//cout<<frt[i][j].first<<" "<<frt[i][j].second<<endl;
			}
		}
	}
}

int main(){
	scanf("%d", &N);
	for(int i=1; i<=N; i++){
		int x;
		scanf("%d", &x);
		if(x>0){
			vt.pb({1, x});
		}else{
			vt.pb({2, -x});
			prv[i-1] = -1;
		}
	}
	make_prv();
	for(int i=0; i<N; i++){
		if(vt[i].first==1){
			num[i] = i;
			pq1.push(num[i]);
			chk[i] = true;
		}else{
			//cout<<"*"<<prv[i]<<endl;
			num[i] = num[prv[i]];
			chk[num[i]] = (!chk[num[i]]);
			if(chk[num[i]]){
				pq1.push(num[i]);
			}else{
				pq2.push(num[i]);
			}
		}
		while(!pq1.empty() && !pq2.empty() && pq1.top()==pq2.top()){
			pq1.pop();
			pq2.pop();
		}
		if(pq1.empty()){
			printf("0\n");
		}
		else printf("%d\n", vt[pq1.top()].second);
	}
}

Compilation message (stderr)

edi.cpp: In function 'int main()':
edi.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
edi.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37