oj.uz

답안 #120011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
120011 2019-06-23T00:03:30 Z E869120 Editor (BOI15_edi) C++14
35 / 100
 84 ms 6512 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[5];

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

# 결과 실행 시간 메모리 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 29 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 48 ms 512 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 38 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 6512 KB Output is correct
2 Correct 82 ms 6508 KB Output is correct

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 3668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 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 29 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 48 ms 512 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 38 ms 384 KB Output is correct
10 Correct 84 ms 6512 KB Output is correct
11 Correct 82 ms 6508 KB Output is correct
12 Runtime error 29 ms 3668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -