Submission #198062

#	Time	Username	Problem	Language	Result	Execution time	Memory
198062		dndhk	Editor (BOI15_edi)	C++14	43 / 100	127 ms	12284 KiB

edi

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int MAX_N = 300000;

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];
int frt[MAX_N+1];

priority_queue<int> pq1, pq2;

vector<int> vc;

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;
		}
		frt[i-1] = N+1;
	}
	for(int i=N-1; i>=0; i--){
		if(vt[i].first==2 && prv[i]==-1){
			v.pb({i, vt[i].second});
			vc.pb(i);
			for(int j=i-1; j>=0; j--){
				if(vt[j].first==2){
					if(v.back().second>vt[j].second){
						prv[v.back().first] = j;
						v.pop_back();
					}else{
						if(prv[j]!=-1){
							j = frt[j];
						}
						else {
							vc.pb(j);
							v.pb({j, vt[j].second});
						}
					}
				}else{
					prv[v.back().first] = j;
					v.pop_back();
				}
				if(v.empty())	break;
			}
			frt[vc.back()] = prv[vc.back()];
			for(int j=vc.size()-2; j>=0; j--){
				if(vc[j+1]==prv[vc[j]]-1){
					frt[vc[j]] = frt[vc[j+1]];
				}else{
					frt[vc[j]] = prv[vc[j]];
				}
			}
			while(!vc.empty())	vc.pop_back();
		}
	}
	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:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
edi.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

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