oj.uz

Submission #338316

# Submission time Handle Problem Language Result Execution time Memory
338316 2020-12-23T01:44:14 Z Kevin_Zhang_TW Editor (BOI15_edi) C++17
35 / 100
 3000 ms 8448 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];

	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 20 ms 492 KB Output is correct
6 Correct 0 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 492 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 7020 KB Output is correct
2 Correct 251 ms 8448 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 7192 KB Output is correct
2 Execution timed out 3076 ms 7352 KB Time limit exceeded
3 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 20 ms 492 KB Output is correct
6 Correct 0 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 492 KB Output is correct
10 Correct 334 ms 7020 KB Output is correct
11 Correct 251 ms 8448 KB Output is correct
12 Correct 148 ms 7192 KB Output is correct
13 Execution timed out 3076 ms 7352 KB Time limit exceeded
14 Halted 0 ms 0 KB -