oj.uz

Submission #389987

# Submission time Handle Problem Language Result Execution time Memory
389987 2021-04-15T03:44:01 Z maximath_1 Editor (BOI15_edi) C++11
0 / 100
 295 ms 116868 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 295 ms 116868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 184 ms 53896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -