Submission #389988

#	Time	Username	Problem	Language	Result	Execution time	Memory
389988		maximath_1	Editor (BOI15_edi)	C++11	100 / 100	419 ms	140868 KiB

edi

#include <bits/stdc++.h>
using namespace std;

const int inf = 2e9 + 69;
int rt[300005], st[12800069][3], sz = 1;
int q, queries[300005];

int copyNode(int x){
	st[sz][0] = st[x][0];
	st[sz][1] = st[x][1];
	st[sz][2] = st[x][2];
	return sz ++;
}

int build(int cl, int cr){
	int nw = sz ++;
	if(cl == cr) return nw;
	int md = (cl + cr) / 2;
	st[nw][0] = build(cl, md);
	st[nw][1] = build(md + 1, cr);
	return nw;
}

int upd(int nw, int cl, int cr, int ps, int x){
	nw = copyNode(nw);
	if(cl == cr){
		st[nw][2] = max(st[nw][2], x);
		return nw;
	}

	int md = (cl + cr) / 2;
	if(ps <= md)
		st[nw][0] = upd(st[nw][0], cl, md, ps, x);
	else
		st[nw][1] = upd(st[nw][1], md + 1, cr, ps, x);
	st[nw][2] = max(st[st[nw][0]][2], st[st[nw][1]][2]);

	return nw;
}

int que(int nw, int cl, int cr, int l, int r){
	if(r < cl || cr < l) return 0;
	if(l <= cl && cr <= r) return st[nw][2];
	int md = (cl + cr) / 2;
	return max(que(st[nw][0], cl, md, l, r), que(st[nw][1], md + 1, cr, l, r));
}

int trans(int nw, int bf, int cl, int cr, int l, int r){
	if(r < cl || cr < l || cl > cr) return nw;
	if(l <= cl && cr <= r) return bf;
	nw = copyNode(nw);

	int md = (cl + cr) / 2;
	st[nw][0] = trans(st[nw][0], st[bf][0], cl, md, l, r);
	st[nw][1] = trans(st[nw][1], st[bf][1], md + 1, cr, l, r);

	st[nw][2] = max(st[st[nw][0]][2], st[st[nw][1]][2]);
	return nw;
}

int main(){
	int tmp;
	scanf("%d", &q);
	for(int i = 1; i <= q; i ++)
		scanf("%d", &queries[i]);

	rt[0] = build(1, q);
	for(int qq = 1; qq <= q; qq ++){
		int a = queries[qq];
		if(a > 0){
			rt[qq] = upd(rt[qq - 1], 0, q, 0, qq);
		}else{
			a *= -1;
			int last_op = que(rt[qq - 1], 0, q, 0, a - 1);

			rt[qq] = trans(rt[qq - 1], rt[last_op - 1], 0, q, 0, a - 1);
			rt[qq] = upd(rt[qq], 0, q, a, qq);
		}
		printf("%d\n", queries[que(rt[qq], 0, q, 0, 0)]);
	}

	return 0;
}

Compilation message (stderr)

edi.cpp: In function 'int main()':
edi.cpp:62:6: warning: unused variable 'tmp' [-Wunused-variable]
   62 |  int tmp;
      |      ^~~
edi.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
edi.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d", &queries[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37