oj.uz

Submission #338315

# Submission time Handle Problem Language Result Execution time Memory
338315 2020-12-23T01:43:11 Z Kevin_Zhang_TW Editor (BOI15_edi) C++17
20 / 100
 27 ms 1516 KB 
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &val, T nv) {
	return val < nv ? (val = nv, true) : false;
}
template<class T>
bool chmin(T &val, T nv) {
	return nv < val ? (val = nv, true) : false;
}
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 300010;
int n, a[MAX_N], on[MAX_N], res[MAX_N], nxt[MAX_N];
set<int> alive;
void toggle(int t) {
	if (alive.count(t)) alive.erase(t);
	else alive.insert(t);
}
int qry() { return alive.empty() ? 0 : a[*alive.rbegin()]; }
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1;i <= n;++i)
		cin >> a[i];

	if (n > 5000) return 1;

	for (int i = 1;i <= n;++i) {
		nxt[i] = -1;
		if (a[i] > 0) {
			toggle(i);
		}
		else {
			for (int j = i - 1;j > 0;--j) if (on[j] && a[i] < a[j]) {
				nxt[i] = j;
				for (int x = j; x != -1 ;x = nxt[x]) {
					if (nxt[x] != -1) assert(on[x] ^ on[ nxt[x] ]);
					on[x] ^= 1;
					if (a[x] > 0) toggle(x);
				}
				break;
			}
			assert(nxt[i] != -1);
		}
		res[i] = qry();
		on[i] = true;
	}

	for (int i = 1;i <= n;++i)
		cout << res[i] << '\n';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 18 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 620 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 1516 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 876 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 18 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Runtime error 27 ms 1516 KB Execution failed because the return code was nonzero
11 Halted 0 ms 0 KB -