oj.uz

Submission #27056

# Submission time Handle Problem Language Result Execution time Memory
27056 2017-07-09T06:30:26 Z 윤교준(#1121) Editor (BOI15_edi) C++11
35 / 100
 3000 ms 193120 KB 
#include <bits/stdc++.h>
#define pb push_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[(sz(V)-2)])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define rb(x) ((x)&(-(x)))
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MAXN (300005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
struct Node {
	Node() : l(NULL), r(NULL), dt(0) {}
	Node *l, *r;
	int dt;
	void makePST(Node *rt, int X, int R, int S = 0, int E = MAXN) {
		dt = R; if(S == E) return;
		int M = (S+E)/2;
		if(X <= M) {
			l = new Node();
			l -> makePST(rt ? rt -> l : NULL, X, R, S, M);
		} else {
			r = new Node();
			r -> makePST(rt ? rt -> r : NULL, X, R, M+1, E);
		}
		if(rt) {
			if(X <= M) r = rt -> r;
			else l = rt -> l;
		}
	}
	int get(int P, int Q, int S = 0, int E = MAXN) {
		if(Q < P) return 0;
		if(P <= S && E <= Q) return dt;
		int M = (S+E)/2;
		return max(l ? l -> get(P, Q, S, M) : 0, r ? r -> get(P, Q, M+1, E) : 0);
	}
};

Node *PST[MAXN];
int A[MAXN];
int N;

int main() {
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
	PST[0] = new Node(); PST[0] -> dt = 0;
	for(int i = 1; i <= N; i++) {
		PST[i] = new Node();
		if(0 < A[i]) {
			PST[i] -> makePST(PST[i-1], 0, i);
		} else {
			int idx = PST[i-1] -> get(0, -A[i]-1);
			PST[i] -> makePST(PST[idx-1], -A[i], i);
		}
	}
	for(int i = 1; i <= N; i++) {
		printf("%d\n", A[PST[i] -> get(0, 0)]);
	}
	return 0;
}

Compilation message

edi.cpp: In function 'int main()':
edi.cpp:53:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
edi.cpp:54:48: 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 0 ms 5548 KB Output is correct
2 Correct 9 ms 8584 KB Output is correct
3 Correct 0 ms 5548 KB Output is correct
4 Correct 0 ms 5548 KB Output is correct
5 Correct 96 ms 8584 KB Output is correct
6 Correct 0 ms 5548 KB Output is correct
7 Correct 6 ms 8716 KB Output is correct
8 Correct 0 ms 5548 KB Output is correct
9 Correct 139 ms 8584 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 193120 KB Output is correct
2 Correct 423 ms 193120 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1946 ms 97552 KB Output is correct
2 Execution timed out 3000 ms 115900 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5548 KB Output is correct
2 Correct 9 ms 8584 KB Output is correct
3 Correct 0 ms 5548 KB Output is correct
4 Correct 0 ms 5548 KB Output is correct
5 Correct 96 ms 8584 KB Output is correct
6 Correct 0 ms 5548 KB Output is correct
7 Correct 6 ms 8716 KB Output is correct
8 Correct 0 ms 5548 KB Output is correct
9 Correct 139 ms 8584 KB Output is correct
10 Correct 366 ms 193120 KB Output is correct
11 Correct 423 ms 193120 KB Output is correct
12 Correct 1946 ms 97552 KB Output is correct
13 Execution timed out 3000 ms 115900 KB Execution timed out
14 Halted 0 ms 0 KB -