oj.uz

답안 #198049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198049 2020-01-24T14:54:14 Z dndhk Editor (BOI15_edi) C++14
43 / 100
 115 ms 12264 KB 
#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] = 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;
			}
		}
		while(!vc.empty()){
			frt[vc.back()] = prv[vc.back()];
			if(prv[vc.back()]!=0)	frt[vc.back()] = min(frt[vc.back()], frt[prv[vc.back()]-1]);
			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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 4 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 11748 KB Output is correct
2 Correct 103 ms 11164 KB Output is correct

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 6136 KB Output is correct
2 Correct 63 ms 7268 KB Output is correct
3 Correct 69 ms 9364 KB Output is correct
4 Correct 109 ms 11696 KB Output is correct
5 Correct 115 ms 12264 KB Output is correct
6 Correct 72 ms 8928 KB Output is correct

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 4 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -