Submission #120011

#	Time	Username	Problem	Language	Result	Execution time	Memory
120011		E869120	Editor (BOI15_edi)	C++14	35 / 100	84 ms	6512 KiB

edi

#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 (stderr)

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 / 20
• Subtask 2: 15 / 15
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37