oj.uz

Submission #402148

# Submission time Handle Problem Language Result Execution time Memory
402148 2021-05-11T11:29:23 Z pavement Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4094 ms 293784 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
 
int N, Q, x, a, b, l, r;
bool A[300005];
char tmp;
string s;
set<pair<int, int> > S;
gp_hash_table<int, int> ft[300005];
 
inline int ls(int x) {
	return x & -x;
}
 
void upd(int l1, int l2, int r1, int r2, int v) {
	// add v to (l1, r1)
	for (int i = l1; i <= N + 1; i += ls(i))
		for (int j = r1; j <= N + 1; j += ls(j))
			ft[i][j] += v;
	
	// add -v to (l1, r2 + 1)
	for (int i = l1; i <= N + 1; i += ls(i))
		for (int j = r2 + 1; j <= N + 1; j += ls(j))
			ft[i][j] -= v;
	
	// add -v to (l2 + 1, r1)
	for (int i = l2 + 1; i <= N + 1; i += ls(i))
		for (int j = r1; j <= N + 1; j += ls(j))
			ft[i][j] -= v;
	
	// add v to (l2 + 1, r2 + 1)
	for (int i = l2 + 1; i <= N + 1; i += ls(i))
		for (int j = r2 + 1; j <= N + 1; j += ls(j))
			ft[i][j] += v;
}
 
int qry(int x, int y) {
	int r = 0;
	for (int i = x; i; i -= ls(i))
		for (int j = y; j; j -= ls(j))
		    if (ft[i].find(j) != ft[i].end()) r += ft[i][j];
	return r;
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		cin >> tmp;
		A[i] = tmp - '0';
		if (A[i]) {
			if (i == 1 || !A[i - 1]) S.emplace(i, i);
			else {
				int lft = S.rbegin()->first;
				S.erase(--S.end());
				S.emplace(lft, i);
			}
		}
	}
	for (int i = 1; i <= Q; i++) {
		cin >> s;
		if (s == "toggle") {
			cin >> x;
			if (A[x]) {
				auto it = S.upper_bound(make_pair(x, (int)1e9));
				assert(it != S.begin());
				--it;
				l = it->first;
				r = it->second + 1;
				
				// fix S
				S.erase(it);
				if (l < x) S.emplace(l, x - 1);
				if (x < r - 1) S.emplace(x + 1, r - 1);
				
				assert(l <= x && x + 1 <= r);
				// we know that [l, x] can currently reach [x + 1, r]
				upd(l, x, x + 1, r, i);
			} else {
				vector<set<pair<int, int> >::iterator> del;
				auto it = S.upper_bound(make_pair(x, (int)1e9));
				if (it != S.end() && it->first == x + 1) r = it->second + 1, del.push_back(it);
				else r = x + 1;
				if (it != S.begin()) {
					--it;
					if (it->second == x - 1) l = it->first, del.push_back(it);
					else l = x;
				} else l = x;
				
				// fix S
				for (auto i : del) S.erase(i);
				S.emplace(l, r - 1);
				
				// we know that [l, x] cannot currently reach [x + 1, r]
				upd(l, x, x + 1, r, -i);
			}
			A[x] ^= 1;
		} else {
			cin >> a >> b;
			auto it = S.upper_bound(make_pair(a, (int)1e9));
			if (it != S.begin()) {
				--it;
				if (b <= it->second + 1) {
					cout << qry(a, b) + i << '\n';
					goto done;
				}
			}
			cout << qry(a, b) << '\n';
			done:;
		}
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 63684 KB Output is correct
2 Correct 66 ms 63712 KB Output is correct
3 Correct 65 ms 63616 KB Output is correct
4 Correct 66 ms 63684 KB Output is correct
5 Correct 66 ms 63684 KB Output is correct
6 Correct 66 ms 63676 KB Output is correct
7 Correct 66 ms 63712 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 67940 KB Output is correct
2 Correct 393 ms 68360 KB Output is correct
3 Correct 765 ms 72428 KB Output is correct
4 Correct 2938 ms 213452 KB Output is correct
5 Correct 2783 ms 220164 KB Output is correct
6 Correct 3119 ms 220072 KB Output is correct
7 Correct 590 ms 70468 KB Output is correct
8 Correct 596 ms 71876 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 64068 KB Output is correct
2 Correct 77 ms 63972 KB Output is correct
3 Correct 73 ms 63972 KB Output is correct
4 Correct 66 ms 63680 KB Output is correct
5 Correct 4094 ms 293784 KB Output is correct
6 Correct 3523 ms 253320 KB Output is correct
7 Correct 2821 ms 219340 KB Output is correct
8 Correct 553 ms 71916 KB Output is correct
9 Correct 186 ms 67540 KB Output is correct
10 Correct 225 ms 67660 KB Output is correct
11 Correct 189 ms 67912 KB Output is correct
12 Correct 528 ms 70448 KB Output is correct
13 Correct 560 ms 72020 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 63684 KB Output is correct
2 Correct 72 ms 63884 KB Output is correct
3 Correct 75 ms 63944 KB Output is correct
4 Correct 74 ms 64008 KB Output is correct
5 Correct 1258 ms 82452 KB Output is correct
6 Correct 2521 ms 195172 KB Output is correct
7 Correct 3166 ms 219968 KB Output is correct
8 Correct 3709 ms 237520 KB Output is correct
9 Correct 460 ms 67588 KB Output is correct
10 Correct 358 ms 66708 KB Output is correct
11 Correct 461 ms 67480 KB Output is correct
12 Correct 349 ms 66628 KB Output is correct
13 Correct 462 ms 67764 KB Output is correct
14 Correct 352 ms 66608 KB Output is correct
15 Correct 546 ms 70672 KB Output is correct
16 Correct 556 ms 71876 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 63684 KB Output is correct
2 Correct 66 ms 63712 KB Output is correct
3 Correct 65 ms 63616 KB Output is correct
4 Correct 66 ms 63684 KB Output is correct
5 Correct 66 ms 63684 KB Output is correct
6 Correct 66 ms 63676 KB Output is correct
7 Correct 66 ms 63712 KB Output is correct
8 Correct 303 ms 67940 KB Output is correct
9 Correct 393 ms 68360 KB Output is correct
10 Correct 765 ms 72428 KB Output is correct
11 Correct 2938 ms 213452 KB Output is correct
12 Correct 2783 ms 220164 KB Output is correct
13 Correct 3119 ms 220072 KB Output is correct
14 Correct 590 ms 70468 KB Output is correct
15 Correct 596 ms 71876 KB Output is correct
16 Correct 73 ms 64068 KB Output is correct
17 Correct 77 ms 63972 KB Output is correct
18 Correct 73 ms 63972 KB Output is correct
19 Correct 66 ms 63680 KB Output is correct
20 Correct 4094 ms 293784 KB Output is correct
21 Correct 3523 ms 253320 KB Output is correct
22 Correct 2821 ms 219340 KB Output is correct
23 Correct 553 ms 71916 KB Output is correct
24 Correct 186 ms 67540 KB Output is correct
25 Correct 225 ms 67660 KB Output is correct
26 Correct 189 ms 67912 KB Output is correct
27 Correct 528 ms 70448 KB Output is correct
28 Correct 560 ms 72020 KB Output is correct
29 Correct 67 ms 63684 KB Output is correct
30 Correct 72 ms 63884 KB Output is correct
31 Correct 75 ms 63944 KB Output is correct
32 Correct 74 ms 64008 KB Output is correct
33 Correct 1258 ms 82452 KB Output is correct
34 Correct 2521 ms 195172 KB Output is correct
35 Correct 3166 ms 219968 KB Output is correct
36 Correct 3709 ms 237520 KB Output is correct
37 Correct 460 ms 67588 KB Output is correct
38 Correct 358 ms 66708 KB Output is correct
39 Correct 461 ms 67480 KB Output is correct
40 Correct 349 ms 66628 KB Output is correct
41 Correct 462 ms 67764 KB Output is correct
42 Correct 352 ms 66608 KB Output is correct
43 Correct 546 ms 70672 KB Output is correct
44 Correct 556 ms 71876 KB Output is correct
45 Correct 156 ms 66080 KB Output is correct
46 Correct 233 ms 66168 KB Output is correct
47 Correct 1452 ms 117224 KB Output is correct
48 Correct 2930 ms 213204 KB Output is correct
49 Correct 215 ms 67792 KB Output is correct
50 Correct 210 ms 67884 KB Output is correct
51 Correct 234 ms 67976 KB Output is correct
52 Correct 238 ms 68300 KB Output is correct
53 Correct 230 ms 68204 KB Output is correct
54 Correct 274 ms 68276 KB Output is correct