oj.uz

Submission #198077

# Submission time Handle Problem Language Result Execution time Memory
198077 2020-01-24T15:55:29 Z dndhk Editor (BOI15_edi) C++14
100 / 100
 262 ms 60380 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 0 ms 1272 KB Output is correct
3 Correct 2 ms 520 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 5 ms 1400 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 1400 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 1372 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 57764 KB Output is correct
2 Correct 156 ms 59100 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 28956 KB Output is correct
2 Correct 96 ms 35844 KB Output is correct
3 Correct 210 ms 45692 KB Output is correct
4 Correct 157 ms 59152 KB Output is correct
5 Correct 172 ms 60124 KB Output is correct
6 Correct 185 ms 57020 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 0 ms 1272 KB Output is correct
3 Correct 2 ms 520 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 5 ms 1400 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 1400 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 1372 KB Output is correct
10 Correct 167 ms 57764 KB Output is correct
11 Correct 156 ms 59100 KB Output is correct
12 Correct 80 ms 28956 KB Output is correct
13 Correct 96 ms 35844 KB Output is correct
14 Correct 210 ms 45692 KB Output is correct
15 Correct 157 ms 59152 KB Output is correct
16 Correct 172 ms 60124 KB Output is correct
17 Correct 185 ms 57020 KB Output is correct
18 Correct 165 ms 59968 KB Output is correct
19 Correct 163 ms 59916 KB Output is correct
20 Correct 262 ms 57052 KB Output is correct
21 Correct 156 ms 59100 KB Output is correct
22 Correct 173 ms 60380 KB Output is correct