oj.uz

Submission #259971

# Submission time Handle Problem Language Result Execution time Memory
259971 2020-08-08T21:22:02 Z islingr Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4058 ms 64748 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 { bool ask; int l, r, t, del; } a[5 * N], b[5 * 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, m) b[i].r = 0; rep(i, m, r) b[i].r = 1;
	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].ask && !b[i].l && !b[i].r) s += b[i].del * (q - b[i].t - 1);
		if (b[i].ask && 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, m) a[i].l = 0; rep(i, m, r) a[i].l = 1;
	merge(a + l, a + m, a + m, a + r, b + l, [&](const auto &a, const auto &b) { return pair(-a.r, a.ask) < pair(-b.r, b.ask); });
	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> zeroes = {-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++] = {0, pre + 1, i, -1, -1};
				a[p++] = {0, pre + 1, i + 1, -1, +1};
			}
		} else zeroes.insert(pre = i);
	}
	zeroes.insert(n);

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

	sort(a, a + p, [&](const auto &a, const auto &b) { return pair(a.l, a.ask) < pair(b.l, b.ask); });
	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 2558 ms 36172 KB Output is correct
2 Correct 2667 ms 36032 KB Output is correct
3 Correct 2732 ms 36224 KB Output is correct
4 Correct 3390 ms 50600 KB Output is correct
5 Correct 3234 ms 45156 KB Output is correct
6 Correct 3231 ms 53164 KB Output is correct
7 Correct 1481 ms 32660 KB Output is correct
8 Correct 1180 ms 18708 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 640 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3798 ms 59644 KB Output is correct
6 Correct 3639 ms 52976 KB Output is correct
7 Correct 3065 ms 43956 KB Output is correct
8 Correct 1435 ms 17704 KB Output is correct
9 Correct 800 ms 14384 KB Output is correct
10 Correct 877 ms 15860 KB Output is correct
11 Correct 823 ms 15720 KB Output is correct
12 Correct 1744 ms 31832 KB Output is correct
13 Correct 1449 ms 17812 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 2159 ms 33276 KB Output is correct
6 Correct 2694 ms 42508 KB Output is correct
7 Correct 3235 ms 52356 KB Output is correct
8 Correct 4058 ms 64748 KB Output is correct
9 Correct 3548 ms 41428 KB Output is correct
10 Correct 3699 ms 49424 KB Output is correct
11 Correct 3383 ms 41420 KB Output is correct
12 Correct 3750 ms 49404 KB Output is correct
13 Correct 3141 ms 41424 KB Output is correct
14 Correct 3726 ms 49428 KB Output is correct
15 Correct 1849 ms 31832 KB Output is correct
16 Correct 1632 ms 17676 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 2558 ms 36172 KB Output is correct
9 Correct 2667 ms 36032 KB Output is correct
10 Correct 2732 ms 36224 KB Output is correct
11 Correct 3390 ms 50600 KB Output is correct
12 Correct 3234 ms 45156 KB Output is correct
13 Correct 3231 ms 53164 KB Output is correct
14 Correct 1481 ms 32660 KB Output is correct
15 Correct 1180 ms 18708 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 640 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 3798 ms 59644 KB Output is correct
21 Correct 3639 ms 52976 KB Output is correct
22 Correct 3065 ms 43956 KB Output is correct
23 Correct 1435 ms 17704 KB Output is correct
24 Correct 800 ms 14384 KB Output is correct
25 Correct 877 ms 15860 KB Output is correct
26 Correct 823 ms 15720 KB Output is correct
27 Correct 1744 ms 31832 KB Output is correct
28 Correct 1449 ms 17812 KB Output is correct
29 Correct 4 ms 512 KB Output is correct
30 Correct 5 ms 512 KB Output is correct
31 Correct 6 ms 512 KB Output is correct
32 Correct 8 ms 512 KB Output is correct
33 Correct 2159 ms 33276 KB Output is correct
34 Correct 2694 ms 42508 KB Output is correct
35 Correct 3235 ms 52356 KB Output is correct
36 Correct 4058 ms 64748 KB Output is correct
37 Correct 3548 ms 41428 KB Output is correct
38 Correct 3699 ms 49424 KB Output is correct
39 Correct 3383 ms 41420 KB Output is correct
40 Correct 3750 ms 49404 KB Output is correct
41 Correct 3141 ms 41424 KB Output is correct
42 Correct 3726 ms 49428 KB Output is correct
43 Correct 1849 ms 31832 KB Output is correct
44 Correct 1632 ms 17676 KB Output is correct
45 Correct 1633 ms 22748 KB Output is correct
46 Correct 1731 ms 22704 KB Output is correct
47 Correct 2033 ms 27780 KB Output is correct
48 Correct 3419 ms 49008 KB Output is correct
49 Correct 1095 ms 17736 KB Output is correct
50 Correct 1097 ms 17796 KB Output is correct
51 Correct 1181 ms 17744 KB Output is correct
52 Correct 941 ms 17688 KB Output is correct
53 Correct 988 ms 17688 KB Output is correct
54 Correct 963 ms 17688 KB Output is correct