oj.uz

답안 #43018

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43018 2018-03-08T05:48:34 Z milmillin Editor (BOI15_edi) C++14
15 / 100
 204 ms 17220 KB 
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int seg[1500000];
vector<int> stk[300100];
bool active[300100];

int get(int idx) {
	if (stk[idx].empty()) return 0;
	return stk[idx].back();
}

void update(int idx, int l, int r, int k) {
	if (k < l || k >= r) return;
	if (l + 1 == r) {
		seg[idx] = get(l);
		return;
	}	
	int m = (l + r) >> 1;
	update(idx * 2 + 1, l, m, k);
	update(idx * 2 + 2, m, r, k);
	seg[idx] = max(seg[idx * 2 + 1], seg[idx * 2 + 2]);
}

int query(int idx, int l, int r, int k) {
	if (k <= l) return 0;
	if (k >= r) return seg[idx];
	int m = (l + r) >> 1;
	return max(query(idx * 2 + 1, l, m, k), query(idx * 2 + 2, m, r, k));
}

int state[300100];
int par[300100];

int main() {
	int n;
	scanf("%d", &n);
	int x,tmp;
	for (int i = 1; i <= n; i++) par[i] = i;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		if (x > 0) {
			active[i] = true;
			stk[0].push_back(i);
			update(0, 0, n + 1, 0);
			state[i] = x;
		} else {
			x = -x;
			tmp = query(0, 0, n + 1, x);
			tmp = par[tmp];
			par[i] = tmp;
			
			if (active[tmp]) stk[0].pop_back();
			else stk[0].push_back(tmp);
			active[tmp] = !active[tmp];
			update(0, 0, n + 1, 0);

			active[i] = true;
			stk[x].push_back(i);
			update(0, 0, n + 1, x);
		}
		printf("%d\n", state[get(0)]);
	}
	return 0;
}

Compilation message

edi.cpp: In function 'int main()':
edi.cpp:40:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
edi.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 7288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 14300 KB Output is correct
2 Correct 176 ms 15584 KB Output is correct

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 127 ms 17220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 7288 KB Output isn't correct
2 Halted 0 ms 0 KB -