oj.uz

Submission #260515

# Submission time Handle Problem Language Result Execution time Memory
260515 2020-08-10T12:32:44 Z islingr Street Lamps (APIO19_street_lamps) C++17
100 / 100
 3501 ms 55268 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)

const int N = 1 << 19;
struct { int l, r, t, del; } a[3 * N], b[3 * N];
int q, ans[N];

void cdq2(int l, int r) {
	if (r - l == 1) return;
	int m = (l + r) >> 1;
	cdq2(l, m); cdq2(m, r);
	rep(i, l, r) b[i].r = i < m;
	inplace_merge(b + l, b + m, b + r, [&](const auto &a, const auto &b) { return a.t < b.t; });
	int s = 0;
	rep(i, l, r) {
		if (b[i].del && b[i].l && b[i].r) s += b[i].del * b[i].t;
		if (!b[i].del && !b[i].l && !b[i].r) ans[b[i].t] += s;
	}
}

void cdq1(int l, int r) {
	if (r - l == 1) return;
	int m = (l + r) >> 1;
	cdq1(l, m); cdq1(m, r);
	rep(i, l, r) a[i].l = i < m;
	merge(a + l, a + m, a + m, a + r, b + l, [&](const auto &a, const auto &b) { return pair(a.r, a.del & 1) > pair(b.r, b.del & 1); });
	rep(i, l, r) a[i] = b[i];
	cdq2(l, r);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, p = 0; cin >> n >> q; int pre = -1;
	set<int> z = {-1};
	rep(i, 0, n) {
		char c; cin >> c;
		if (c != '0') {
			if (p && a[p - 1].r == i) a[p - 1].r = i + 1;
			else a[p++] = {pre + 1, i + 1, -1, -1};
		} else z.insert(pre = i);
	}
	z.insert(n);

	rep(t, 0, q) {
		string s; cin >> s;
		if (s == "toggle") {
			int i; cin >> i; --i;
			auto [it, f] = z.insert(i);
			int d = f ? +1 : -1;
			a[p++] = {*prev(it) + 1, *next(it), t, +d};
			a[p++] = {*prev(it) + 1, i, t, -d};
			a[p++] = {i + 1, *next(it), t, -d};
			if (d < 0) z.erase(it);
			ans[t] = -1;
		} else {
			int l, r; cin >> l >> r; --l; --r;
			a[p++] = {l, r, t, 0};
			ans[t] = *z.lower_bound(l) < r ? 0 : t;
		}
	}

	sort(a, a + p, [&](const auto &a, const auto &b) { return pair(-a.l, a.del & 1) > pair(-b.l, b.del & 1); });
	cdq1(0, p);
	rep(t, 0, q) if (0 <= ans[t]) cout << ans[t] << '\n';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2369 ms 30648 KB Output is correct
2 Correct 2522 ms 31132 KB Output is correct
3 Correct 2594 ms 31656 KB Output is correct
4 Correct 3018 ms 43028 KB Output is correct
5 Correct 2911 ms 36456 KB Output is correct
6 Correct 2872 ms 45564 KB Output is correct
7 Correct 1509 ms 34640 KB Output is correct
8 Correct 1196 ms 20432 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3453 ms 55268 KB Output is correct
6 Correct 3146 ms 47016 KB Output is correct
7 Correct 2749 ms 36604 KB Output is correct
8 Correct 1477 ms 20432 KB Output is correct
9 Correct 744 ms 14596 KB Output is correct
10 Correct 851 ms 15944 KB Output is correct
11 Correct 797 ms 16060 KB Output is correct
12 Correct 1677 ms 34560 KB Output is correct
13 Correct 1422 ms 20432 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 416 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 1893 ms 31204 KB Output is correct
6 Correct 2415 ms 38088 KB Output is correct
7 Correct 2879 ms 45280 KB Output is correct
8 Correct 3482 ms 54772 KB Output is correct
9 Correct 2912 ms 36896 KB Output is correct
10 Correct 3467 ms 42920 KB Output is correct
11 Correct 2901 ms 36828 KB Output is correct
12 Correct 3501 ms 42912 KB Output is correct
13 Correct 2915 ms 36844 KB Output is correct
14 Correct 3474 ms 42888 KB Output is correct
15 Correct 1683 ms 34752 KB Output is correct
16 Correct 1409 ms 20464 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2369 ms 30648 KB Output is correct
9 Correct 2522 ms 31132 KB Output is correct
10 Correct 2594 ms 31656 KB Output is correct
11 Correct 3018 ms 43028 KB Output is correct
12 Correct 2911 ms 36456 KB Output is correct
13 Correct 2872 ms 45564 KB Output is correct
14 Correct 1509 ms 34640 KB Output is correct
15 Correct 1196 ms 20432 KB Output is correct
16 Correct 6 ms 512 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 5 ms 512 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 3453 ms 55268 KB Output is correct
21 Correct 3146 ms 47016 KB Output is correct
22 Correct 2749 ms 36604 KB Output is correct
23 Correct 1477 ms 20432 KB Output is correct
24 Correct 744 ms 14596 KB Output is correct
25 Correct 851 ms 15944 KB Output is correct
26 Correct 797 ms 16060 KB Output is correct
27 Correct 1677 ms 34560 KB Output is correct
28 Correct 1422 ms 20432 KB Output is correct
29 Correct 4 ms 416 KB Output is correct
30 Correct 4 ms 512 KB Output is correct
31 Correct 5 ms 512 KB Output is correct
32 Correct 6 ms 512 KB Output is correct
33 Correct 1893 ms 31204 KB Output is correct
34 Correct 2415 ms 38088 KB Output is correct
35 Correct 2879 ms 45280 KB Output is correct
36 Correct 3482 ms 54772 KB Output is correct
37 Correct 2912 ms 36896 KB Output is correct
38 Correct 3467 ms 42920 KB Output is correct
39 Correct 2901 ms 36828 KB Output is correct
40 Correct 3501 ms 42912 KB Output is correct
41 Correct 2915 ms 36844 KB Output is correct
42 Correct 3474 ms 42888 KB Output is correct
43 Correct 1683 ms 34752 KB Output is correct
44 Correct 1409 ms 20464 KB Output is correct
45 Correct 1407 ms 20316 KB Output is correct
46 Correct 1578 ms 20704 KB Output is correct
47 Correct 1687 ms 24996 KB Output is correct
48 Correct 2826 ms 43112 KB Output is correct
49 Correct 998 ms 18000 KB Output is correct
50 Correct 1008 ms 18092 KB Output is correct
51 Correct 989 ms 18252 KB Output is correct
52 Correct 884 ms 18508 KB Output is correct
53 Correct 869 ms 18612 KB Output is correct
54 Correct 888 ms 18508 KB Output is correct