oj.uz

Submission #252415

# Submission time Handle Problem Language Result Execution time Memory
252415 2020-07-25T13:44:34 Z Blagojce Editor (BOI15_edi) C++11
35 / 100
 588 ms 4856 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 brute_force(){
	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 e1u1(){
	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;
	}

}

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){
		brute_force();
	}
	else if(subtask2){
		e1u1();
	}
}

 
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 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 43 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 588 ms 4856 KB Output is correct
2 Correct 581 ms 4856 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 896 KB Unexpected end of file - int32 expected
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 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 43 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 588 ms 4856 KB Output is correct
11 Correct 581 ms 4856 KB Output is correct
12 Incorrect 16 ms 896 KB Unexpected end of file - int32 expected
13 Halted 0 ms 0 KB -