oj.uz

Submission #252429

# Submission time Handle Problem Language Result Execution time Memory
252429 2020-07-25T14:43:00 Z Blagojce Editor (BOI15_edi) C++11
63 / 100
 681 ms 21240 KB 
#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 5e5;


int n;

int a[mxn];

void sub1(){
	bool ok[n];
	memset(ok, false, sizeof(ok));
	int ans = -1;
	
	int pr[n];
	memset(pr, -1, sizeof(pr));
	
	fr(i, 0, n){
		ok[i] = true;
		if(a[i] > 0){
			ans = i;
		}
		else{
			int pos = i;
			for(int j = i-1; j >= 0; j --){
				if(!ok[j]) continue;
				if(a[j] > 0){
					pr[pos] = j;
					ok[j] = false;
					break;
				} 
				else if(a[j] > a[pos]){
					pr[pos] = j;
					ok[j] = false;
					
					if(pr[j] == -1){
						break;
					}
					else{
						pos = pr[j];
						pr[j] = -1;
						
						ok[pos] = true;
						j = pos;		
						if(a[pos] >0) break;
					}
				}
			}
		}
		ans = i;
		while(ans >= 0 && (!ok[ans] || a[ans] < 0)){
			--ans;
		} 
		
		if(ans == -1){
			cout<<0<<endl;
		}
		else{
			cout<<a[ans] << endl;
		}
	}
}
void sub2(){
	int pr[n];
	memset(pr, -1, sizeof(pr));
	int ans = -1;
	fr(i, 0, n){
		if(a[i] < 0){
			if(ans != -1){
				ans = pr[ans];
			}
		}
		else{
			pr[i] = ans;
			ans = i;	
		}
		if(ans == -1) cout<<0<<endl;
		else cout<<a[ans]<<endl;
	}
}

int bit[mxn];
void update(int k, int val){
	while(k < mxn){
		bit[k] += val;
		k += k&-k;	
	}
}

int sum(int k){
	int s = 0;
	while(k > 0){
		s += bit[k];
		k -= k&-k;
	}
	return s;
}
int f(int p){
	int cnt = sum(p);
	int temp = 0;
	for(int i = 20; i >= 0; i --){
		if((1<<i) + temp < p){
			if(bit[temp+(1<<i)] < cnt){
				temp += (1<<i);
				cnt -= bit[temp];
			}
		}
	}
	if(temp == 0){
		if(bit[1]) return 1;
		else return 0;
	}
	return temp+1;
}
	vector<int> pos[mxn];
	bool ok[mxn];
void sub3(){	
	fr(i, 0, n){
		ok[i+1] = true;
		if(a[i] < 0){
			pos[-a[i]].pb(i+1);
		}
		update(i+1, 1);
	}
	
	
	
	for(int i = n; i >= 1; i --){
		for(auto u : pos[i]) if(ok[u]) update(u, -1);
		
		for(auto u : pos[i]){
			if(!ok[u]) continue;
			
			int ps = f(u);
			if(ps != 0){
				ok[ps] = false;
				update(ps, -1);
			}
		}
	}
	fr(i, 0, n-1) cout<<0<<endl;
	cout<<a[f(n+1)-1]<<endl;
	
}


void solve(){
	cin >> n;
	
	
	bool subtask1 = n<=5000;
	bool subtask2 = true;
	fr(i, 0, n){
		cin >> a[i];
		if(a[i] < -1) subtask2 = false;
	}
	
	if(subtask1){
		sub1();
	}
	else if(subtask2){
		sub2();
	}
	else{
		sub3();
	}
}

 
int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12032 KB Output is correct
2 Correct 38 ms 12160 KB Output is correct
3 Correct 7 ms 12032 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 56 ms 12160 KB Output is correct
6 Correct 10 ms 12032 KB Output is correct
7 Correct 17 ms 12160 KB Output is correct
8 Correct 7 ms 12032 KB Output is correct
9 Correct 16 ms 12160 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 16376 KB Output is correct
2 Correct 621 ms 16376 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 15608 KB Output is correct
2 Correct 387 ms 16632 KB Output is correct
3 Correct 533 ms 18808 KB Output is correct
4 Correct 624 ms 17912 KB Output is correct
5 Correct 681 ms 21240 KB Output is correct
6 Correct 582 ms 15864 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12032 KB Output is correct
2 Correct 38 ms 12160 KB Output is correct
3 Correct 7 ms 12032 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 56 ms 12160 KB Output is correct
6 Correct 10 ms 12032 KB Output is correct
7 Correct 17 ms 12160 KB Output is correct
8 Correct 7 ms 12032 KB Output is correct
9 Correct 16 ms 12160 KB Output is correct
10 Correct 637 ms 16376 KB Output is correct
11 Correct 621 ms 16376 KB Output is correct
12 Correct 319 ms 15608 KB Output is correct
13 Correct 387 ms 16632 KB Output is correct
14 Correct 533 ms 18808 KB Output is correct
15 Correct 624 ms 17912 KB Output is correct
16 Correct 681 ms 21240 KB Output is correct
17 Correct 582 ms 15864 KB Output is correct
18 Incorrect 672 ms 21136 KB Output isn't correct
19 Halted 0 ms 0 KB -