oj.uz

Submission #27036

# Submission time Handle Problem Language Result Execution time Memory
27036 2017-07-09T05:51:49 Z 김현수(#1118) Editor (BOI15_edi) C++14
100 / 100
 703 ms 211872 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 300005;

int n, a[N];

struct node {
	int v; node *lc, *rc;
	node () {v=0; lc=NULL; rc=NULL;}
	void init (int L=0, int R=n) {
		if(L == R) return;
		int M = (L+R)/2;
		lc = new node(); lc->init(L, M);
		rc = new node(); rc->init(M+1, R);
	}
	void upd (node *Q, int P, int V, int L=0, int R=n) {
		if(L == R) {v = max(Q->v, V); return;}
		int M = (L+R)/2;
		if(P <= M) {
			rc = Q->rc; lc = new node();
			lc->upd(Q->lc, P, V, L, M);
		}
		else {
			lc = Q->lc; rc = new node();
			rc->upd(Q->rc, P, V, M+1, R);
		}
		v = max(lc->v, rc->v);
	}
	int get (int S, int E, int L=0, int R=n) {
		if(S <= L && R <= E) return v;
		if(E < L || R < S) return 0;
		int T = 0, M = (L+R)/2;
		if(lc) T = max(T, lc->get(S, E, L, M));
		if(rc) T = max(T, rc->get(S, E, M+1, R));
		return T;
	}
} *rt[N];

int main()
{
	scanf("%d",&n);
	rt[0] = new node();
	rt[0]->init();
	for(int i=1;i<=n;i++) {
		int T; scanf("%d",&T);
		rt[i] = new node();
		if(T < 0) {
			int I = rt[i-1]->get(0, -T-1);
			rt[i]->upd(rt[I-1], -T, i);
			a[i] = a[I-1];
		}
		else {
			rt[i]->upd(rt[i-1], 0, i);
			a[i] = T;
		}
		printf("%d\n",a[i]);
	}
}

Compilation message

edi.cpp: In function 'int main()':
edi.cpp:41:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
edi.cpp:45:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int T; scanf("%d",&T);
                        ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5556 KB Output is correct
2 Correct 0 ms 8064 KB Output is correct
3 Correct 0 ms 5556 KB Output is correct
4 Correct 0 ms 5556 KB Output is correct
5 Correct 6 ms 7932 KB Output is correct
6 Correct 0 ms 5556 KB Output is correct
7 Correct 6 ms 8064 KB Output is correct
8 Correct 0 ms 5556 KB Output is correct
9 Correct 3 ms 8064 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 211872 KB Output is correct
2 Correct 299 ms 211872 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 102312 KB Output is correct
2 Correct 246 ms 122376 KB Output is correct
3 Correct 323 ms 162372 KB Output is correct
4 Correct 363 ms 211872 KB Output is correct
5 Correct 619 ms 208308 KB Output is correct
6 Correct 346 ms 211872 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5556 KB Output is correct
2 Correct 0 ms 8064 KB Output is correct
3 Correct 0 ms 5556 KB Output is correct
4 Correct 0 ms 5556 KB Output is correct
5 Correct 6 ms 7932 KB Output is correct
6 Correct 0 ms 5556 KB Output is correct
7 Correct 6 ms 8064 KB Output is correct
8 Correct 0 ms 5556 KB Output is correct
9 Correct 3 ms 8064 KB Output is correct
10 Correct 359 ms 211872 KB Output is correct
11 Correct 299 ms 211872 KB Output is correct
12 Correct 186 ms 102312 KB Output is correct
13 Correct 246 ms 122376 KB Output is correct
14 Correct 323 ms 162372 KB Output is correct
15 Correct 363 ms 211872 KB Output is correct
16 Correct 619 ms 208308 KB Output is correct
17 Correct 346 ms 211872 KB Output is correct
18 Correct 549 ms 208308 KB Output is correct
19 Correct 473 ms 208308 KB Output is correct
20 Correct 466 ms 204876 KB Output is correct
21 Correct 393 ms 211872 KB Output is correct
22 Correct 703 ms 208308 KB Output is correct