oj.uz

Submission #120010

# Submission time Handle Problem Language Result Execution time Memory
120010 2019-06-23T00:02:51 Z E869120 Editor (BOI15_edi) C++14
20 / 100
 83 ms 6468 KB 
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

int N, A[300009], P[300009], par[300009];
priority_queue<int, vector<int>, less<int>>Q[3];

void solve_subtask1() {
	for (int i = 1; i <= N; i++) {
		if (A[i] >= 0) {
			P[i] = 1;
		}
		else {
			P[i] = 1;
			for (int j = i - 1; j >= 1; j--) {
				int level = 0; if (A[j] < 0) level = -A[j];
				if (level < -A[i] && P[j] == 1) { par[i] = j; break; }
			}
			int cx = i;
			while (A[cx] < 0) {
				cx = par[cx];
				P[cx] ^= 1;
			}
		}

		int ans = 0;
		for (int j = 1; j <= i; j++) {
			if (P[j] == 1 && A[j] >= 1) ans = A[j];
		}
		cout << ans << endl;
	}
}

void solve_subtask2() {
	P[0] = 1; Q[0].push(0);
	for (int i = 1; i <= N; i++) {
		if (A[i] >= 0) {
			P[i] = 1; Q[0].push(i);
		}
		else {
			P[i] = 1; Q[-A[i]].push(i); int maxn = -1;
			for (int j = -A[i] - 1; j >= 0; j--) {
				if (!Q[j].empty()) maxn = max(maxn, Q[j].top());
			}
			par[i] = maxn;
			int cx = i;
			while (A[cx] < 0) {
				cx = par[cx];
				P[cx] ^= 1; Q[max(-A[cx], 0)].push(cx);
			}
		}

		for (int i = 0; i <= 3; i++) {
			while (!Q[i].empty()) { int pos = Q[i].top(); if (P[pos] == 0) Q[i].pop(); else break; }
		}

		printf("%d\n", A[(int)Q[0].top()]);
	}
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
	if (N <= 5000) solve_subtask1();
	else solve_subtask2();
	return 0;
}

Compilation message

edi.cpp:7:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
edi.cpp: In function 'int main()':
edi.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
edi.cpp:67:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
                               ~~~~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 21 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 31 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 47 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 38 ms 384 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 6468 KB Output is correct
2 Runtime error 38 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 3568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 21 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 31 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 47 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 38 ms 384 KB Output is correct
10 Correct 83 ms 6468 KB Output is correct
11 Runtime error 38 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)