Submission #27091

#	Time	Username	Problem	Language	Result	Execution time	Memory
27091		khsoo01	Editor (BOI15_edi)	C++11	100 / 100	683 ms	211872 KiB

edi

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

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