oj.uz

답안 #198064

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198064 2020-01-24T15:10:06 Z dndhk Editor (BOI15_edi) C++14
35 / 100
 3000 ms 10352 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-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 && vt[vc[j+1]].second>vt[vc[j]].second){
					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

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
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 632 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 552 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 10352 KB Output is correct
2 Correct 107 ms 9792 KB Output is correct

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 5172 KB Output is correct
2 Correct 69 ms 6084 KB Output is correct
3 Execution timed out 3014 ms 5092 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 632 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 552 KB Output is correct
10 Correct 104 ms 10352 KB Output is correct
11 Correct 107 ms 9792 KB Output is correct
12 Correct 46 ms 5172 KB Output is correct
13 Correct 69 ms 6084 KB Output is correct
14 Execution timed out 3014 ms 5092 KB Time limit exceeded
15 Halted 0 ms 0 KB -