oj.uz

Submission #252418

# Submission time Handle Problem Language Result Execution time Memory
252418 2020-07-25T13:58:55 Z Blagojce Editor (BOI15_edi) C++11
35 / 100
 613 ms 7416 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 f(int p){
	int temp = 0;
	for(int i = 20; i >= 0; i --){
		if((1<<i) + temp < p){
			if(bit[temp+(1<<i)]){
				temp += (1<<i);
			}
		}
	}
	return temp;
}

void sub3(){
	
	vector<int> pos[n+1];
	
	bool ok[n+1];
	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]) update(u, -1);
		for(auto u : pos[i]){
			if(!ok[u]) continue;
			
			int ps = f(u);
			if(ps != 0) ok[ps] = false;
		}
	}
	int ans = 0;
	for(int i = n; i >= 1; i --){
		if(ok[i] && a[i-1] > 0){
			ans = a[i-1];
			break;
		}
	}
	fr(i, 0, n-1) cout<<0<<endl;
	cout<<ans<<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 0 ms 384 KB Output is correct
2 Correct 24 ms 464 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 41 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 12 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 10 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 4728 KB Output is correct
2 Correct 606 ms 4700 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 328 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 24 ms 464 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 41 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 12 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 10 ms 384 KB Output is correct
10 Correct 613 ms 4728 KB Output is correct
11 Correct 606 ms 4700 KB Output is correct
12 Incorrect 328 ms 7416 KB Output isn't correct
13 Halted 0 ms 0 KB -