oj.uz

답안 #198076

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198076 2020-01-24T15:54:11 Z dndhk Editor (BOI15_edi) C++14
0 / 100
 107 ms 21472 KB 
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int MAX_N = 300000;
const int MAX_K = 4;

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

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

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 37.0

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