oj.uz

Submission #252421

# Submission time Handle Problem Language Result Execution time Memory
252421 2020-07-25T14:08:31 Z Blagojce Editor (BOI15_edi) C++11
35 / 100
 623 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 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;
}

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 1 ms 384 KB Output is correct
2 Correct 24 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 42 ms 576 KB Output is correct
6 Correct 1 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 11 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 4732 KB Output is correct
2 Correct 623 ms 4728 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 323 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 1 ms 384 KB Output is correct
2 Correct 24 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 42 ms 576 KB Output is correct
6 Correct 1 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 11 ms 384 KB Output is correct
10 Correct 610 ms 4732 KB Output is correct
11 Correct 623 ms 4728 KB Output is correct
12 Incorrect 323 ms 7416 KB Output isn't correct
13 Halted 0 ms 0 KB -