Submission #22981

# Submission time Handle Problem Language Result Execution time Memory
22981 2017-05-01T02:16:53 Z model_code Editor (BOI15_edi) C++11
100 / 100
586 ms 266708 KB
// Jan Kanty Milczek

#include <cstdio>

int max(int x, int y) {
	if (x > y)
		return x;
	else
		return y;
}
int max(int x, int y, int z) {
	return max(x, max(y, z));
}

struct PersTree {
	PersTree *l, *r;
	int key;
	int value;
	int max_value;

	int find(int) const;
	PersTree *add(int, int) const;

	PersTree(PersTree *_l, PersTree *_r, int _key, int _value, int _max_value) : l(_l), r(_r), key(_key), value(_value), max_value(_max_value) {}

};

int safe_max_value(PersTree *x) {
	if (x == NULL)
		return 0;
	return x->max_value;
}

int PersTree::find(int mxkey) const {
	if (mxkey < key)
		return l->find(mxkey);
	else if (mxkey == key)
		return max(safe_max_value(l), value);
	else // if (mxkey > key)
		return max(safe_max_value(l), value, r->find(mxkey));
}

PersTree *PersTree::add(int _key, int nvalue) const {
	PersTree *_l = l;
	PersTree *_r = r;
	int _value = value;

	if (_key < key)
		_l = l->add(_key, nvalue);
	else if (_key == key)
		_value = nvalue;
	else // if (_key > key)
		_r = r->add(_key, nvalue);

	return new PersTree(_l, _r, key, _value, max(safe_max_value(_l), _value, safe_max_value(_r)));
}

PersTree *create_pers_tree(int left, int right) {
	if (left > right)
		return NULL;
	int s = (left + right) / 2;
	return new PersTree(create_pers_tree(left, s - 1), create_pers_tree(s + 1, right), s, 0, 0);
}

int n;
const int M = 3e5 + 5;
PersTree *akt[M];
int wyn[M];
int main() {
	scanf("%d", &n);
	akt[0] = create_pers_tree(0, n);
	wyn[0] = 0;

	for (int i = 1; i <= n; ++i) {
		int op;
		scanf("%d", &op);
		if (op > 0) {
			wyn[i] = op;
			akt[i] = akt[i-1]->add(0, i);
		} else {
			int cof = akt[i-1]->find(-op-1) - 1;
			wyn[i] = wyn[cof];
			akt[i] = akt[cof]->add(-op, i);
		}
    printf("%d\n", wyn[i]);
	}
}

Compilation message

edi.cpp: In function 'int main()':
edi.cpp:70:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
edi.cpp:76:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &op);
                   ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 4688 KB Output is correct
2 Correct 3 ms 7724 KB Output is correct
3 Correct 0 ms 4688 KB Output is correct
4 Correct 0 ms 4688 KB Output is correct
5 Correct 3 ms 7592 KB Output is correct
6 Correct 0 ms 4688 KB Output is correct
7 Correct 0 ms 7592 KB Output is correct
8 Correct 0 ms 4688 KB Output is correct
9 Correct 3 ms 7724 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 296 ms 264860 KB Output is correct
2 Correct 306 ms 264860 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 236 ms 128636 KB Output is correct
2 Correct 239 ms 154640 KB Output is correct
3 Correct 306 ms 206120 KB Output is correct
4 Correct 333 ms 264860 KB Output is correct
5 Correct 586 ms 266576 KB Output is correct
6 Correct 313 ms 264860 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 4688 KB Output is correct
2 Correct 3 ms 7724 KB Output is correct
3 Correct 0 ms 4688 KB Output is correct
4 Correct 0 ms 4688 KB Output is correct
5 Correct 3 ms 7592 KB Output is correct
6 Correct 0 ms 4688 KB Output is correct
7 Correct 0 ms 7592 KB Output is correct
8 Correct 0 ms 4688 KB Output is correct
9 Correct 3 ms 7724 KB Output is correct
10 Correct 296 ms 264860 KB Output is correct
11 Correct 306 ms 264860 KB Output is correct
12 Correct 236 ms 128636 KB Output is correct
13 Correct 239 ms 154640 KB Output is correct
14 Correct 306 ms 206120 KB Output is correct
15 Correct 333 ms 264860 KB Output is correct
16 Correct 586 ms 266576 KB Output is correct
17 Correct 313 ms 264860 KB Output is correct
18 Correct 529 ms 266576 KB Output is correct
19 Correct 399 ms 266576 KB Output is correct
20 Correct 419 ms 261428 KB Output is correct
21 Correct 296 ms 264860 KB Output is correct
22 Correct 543 ms 266708 KB Output is correct