oj.uz

Submission #389988

# Submission time Handle Problem Language Result Execution time Memory
389988 2021-04-15T03:44:40 Z maximath_1 Editor (BOI15_edi) C++11
100 / 100
 419 ms 140868 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", &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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 4 ms 1612 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 5 ms 1860 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 4 ms 1616 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 5 ms 1644 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 115428 KB Output is correct
2 Correct 294 ms 116932 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 53028 KB Output is correct
2 Correct 197 ms 65224 KB Output is correct
3 Correct 327 ms 110788 KB Output is correct
4 Correct 322 ms 116900 KB Output is correct
5 Correct 417 ms 113356 KB Output is correct
6 Correct 289 ms 114884 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 4 ms 1612 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 5 ms 1860 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 4 ms 1616 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 5 ms 1644 KB Output is correct
10 Correct 298 ms 115428 KB Output is correct
11 Correct 294 ms 116932 KB Output is correct
12 Correct 182 ms 53028 KB Output is correct
13 Correct 197 ms 65224 KB Output is correct
14 Correct 327 ms 110788 KB Output is correct
15 Correct 322 ms 116900 KB Output is correct
16 Correct 417 ms 113356 KB Output is correct
17 Correct 289 ms 114884 KB Output is correct
18 Correct 400 ms 113228 KB Output is correct
19 Correct 343 ms 113060 KB Output is correct
20 Correct 412 ms 140868 KB Output is correct
21 Correct 348 ms 116932 KB Output is correct
22 Correct 419 ms 113128 KB Output is correct