제출 #389987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
389987		maximath_1	Editor (BOI15_edi)	C++11	0 / 100	295 ms	116868 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 %d", &q, &tmp);
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

edi.cpp: In function 'int main()':
edi.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |  scanf("%d %d", &q, &tmp);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
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: 0 / 20
• Subtask 2: 0 / 15
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37