oj.uz

Submission #521227

# Submission time Handle Problem Language Result Execution time Memory
521227 2022-02-01T08:57:32 Z sidon Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1607 ms 122156 KB 
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define all(X) begin(X), end(X)
 
struct BIT {
	vector<int> a; int n, sum = 0;
 
	BIT(int N) : a((n=N)+1) {}
 
	void add(int i, int v) {
		sum += v;
		for(++i; i <= n; i += i&-i) a[i] += v;
	}
	int get(int i) {
		int v = 0;
		for(++i; i >= 1; i -= i&-i) v += a[i];
		return v;
	}
	int suf(int i) { // [i...)
		return sum - get(i-1); }
};
 
const int Z = 3e5+1;

struct CompoundBIT {
	int n;
	vector<vi> a;
	vector<BIT*> b;
 
	CompoundBIT(int N) : n(N), a(N), b(N) {}
 
	void addVal(int i, int v) {
		for(++i; i < n; i += i&-i) a[i].push_back(v);
	}
	void build() {
		for(int i = 1; i < n; i++) {
			sort(all(a[i]));
			b[i] = new BIT(size(a[i]));
		}
	}
	void update(int i, int v, int w) {
		for(++i; i < n; i += i&-i) 
			b[i]->add(lower_bound(all(a[i]), v) - begin(a[i]), w);
	}
	int query(int i, int v) {
		int x = 0;
		for(++i; i > 0; i -= i&-i)
			x += b[i]->suf(lower_bound(all(a[i]), v) - begin(a[i]));
		return x;
	}
} cb(Z);
 
int N, Q;
string _inp;
 
int qL[Z], qR[Z];
bitset<Z> qType, state;
 
set<array<int, 2>> intervals;
vector<array<int, 3>> iAt[Z];
array<int, 2> iFound[Z];
map<int, int> last[Z];
 
void addInterval(int l, int r, int i) {
	if(r < l) return;
	cb.addVal(l, r);
	intervals.insert({l, r});
	iAt[i].push_back({l, r, 1});
}
 
void remInterval(int l, int r, int i) {
	if(r < l) return;
	intervals.erase({l, r});
	iAt[i].push_back({l, r, 0});
}
 
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
 	cin >> N >> Q;
	cin >> _inp;
 
	for(int i = 0; i < N; ++i)
		state[i] = _inp[i] - '0';
 
	for(int i = 0; i < N; ++i) if(state[i]) {
		int l = i;
		while(i < N && state[i]) ++i;
		addInterval(l, i-1, 0);
	}
 
	for(int i = 1; i <= Q; ++i) {
		cin >> _inp >> qL[i]; --qL[i];
 
		if((qType[i] = _inp[0] == 'q')) {
			cin >> qR[i];
			qR[i] -= 2;
			auto f = intervals.upper_bound({qL[i], Z});
			if(!empty(intervals) && f != begin(intervals))
				iFound[i] = *--f;
			else
				iFound[i][0] = Z;
		} else {
			auto f = intervals.upper_bound({qL[i], Z});
			int v = qL[i];
			if(state[v]) {
				auto [l, r] = *--f;
				remInterval(l, r, i);
				addInterval(l, v-1, i);
				addInterval(v+1, r, i);
			} else {
				int l = v, r = v;
				if(v + 1 < N && state[v+1]) r = (*f)[1];
				if(v + 0 > 0 && state[v-1]) l = (*--f)[0];
				remInterval(v+1, r, i);
				remInterval(l, v-1, i);
				addInterval(l, r, i);
			}
			state[v] = !state[v];
		}
	}
	cb.build();
 
	for(int i = 0; i <= Q; ++i) {
		for(auto &[l, r, toAdd] : iAt[i]) {
			if(toAdd) last[l][r] = i;
			else cb.update(l, r, i - last[l][r]);
		}
		if(qType[i]) {
			int res = cb.query(qL[i], qR[i]);
			auto [l, r] = iFound[i];
			if(l <= qL[i] && qR[i] <= r)
				res += i - last[l][r];
			cout << res << '\n';
		}
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 54276 KB Output is correct
2 Correct 36 ms 54360 KB Output is correct
3 Correct 41 ms 54272 KB Output is correct
4 Correct 36 ms 54348 KB Output is correct
5 Correct 35 ms 54352 KB Output is correct
6 Correct 35 ms 54356 KB Output is correct
7 Correct 35 ms 54288 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 84904 KB Output is correct
2 Correct 785 ms 84104 KB Output is correct
3 Correct 890 ms 83656 KB Output is correct
4 Correct 1064 ms 101644 KB Output is correct
5 Correct 1080 ms 95868 KB Output is correct
6 Correct 1130 ms 103708 KB Output is correct
7 Correct 210 ms 59956 KB Output is correct
8 Correct 185 ms 61340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 54560 KB Output is correct
2 Correct 37 ms 54436 KB Output is correct
3 Correct 37 ms 54536 KB Output is correct
4 Correct 36 ms 54316 KB Output is correct
5 Correct 1484 ms 114264 KB Output is correct
6 Correct 1365 ms 107780 KB Output is correct
7 Correct 1054 ms 95116 KB Output is correct
8 Correct 192 ms 61264 KB Output is correct
9 Correct 116 ms 58948 KB Output is correct
10 Correct 129 ms 59340 KB Output is correct
11 Correct 111 ms 59440 KB Output is correct
12 Correct 176 ms 59952 KB Output is correct
13 Correct 192 ms 61276 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 54340 KB Output is correct
2 Correct 44 ms 54468 KB Output is correct
3 Correct 40 ms 54540 KB Output is correct
4 Correct 37 ms 54620 KB Output is correct
5 Correct 511 ms 77896 KB Output is correct
6 Correct 796 ms 92000 KB Output is correct
7 Correct 1134 ms 103172 KB Output is correct
8 Correct 1607 ms 122156 KB Output is correct
9 Correct 1000 ms 92608 KB Output is correct
10 Correct 1111 ms 104424 KB Output is correct
11 Correct 992 ms 92736 KB Output is correct
12 Correct 1091 ms 104520 KB Output is correct
13 Correct 1027 ms 92724 KB Output is correct
14 Correct 1079 ms 104436 KB Output is correct
15 Correct 196 ms 59924 KB Output is correct
16 Correct 191 ms 61476 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 54276 KB Output is correct
2 Correct 36 ms 54360 KB Output is correct
3 Correct 41 ms 54272 KB Output is correct
4 Correct 36 ms 54348 KB Output is correct
5 Correct 35 ms 54352 KB Output is correct
6 Correct 35 ms 54356 KB Output is correct
7 Correct 35 ms 54288 KB Output is correct
8 Correct 637 ms 84904 KB Output is correct
9 Correct 785 ms 84104 KB Output is correct
10 Correct 890 ms 83656 KB Output is correct
11 Correct 1064 ms 101644 KB Output is correct
12 Correct 1080 ms 95868 KB Output is correct
13 Correct 1130 ms 103708 KB Output is correct
14 Correct 210 ms 59956 KB Output is correct
15 Correct 185 ms 61340 KB Output is correct
16 Correct 39 ms 54560 KB Output is correct
17 Correct 37 ms 54436 KB Output is correct
18 Correct 37 ms 54536 KB Output is correct
19 Correct 36 ms 54316 KB Output is correct
20 Correct 1484 ms 114264 KB Output is correct
21 Correct 1365 ms 107780 KB Output is correct
22 Correct 1054 ms 95116 KB Output is correct
23 Correct 192 ms 61264 KB Output is correct
24 Correct 116 ms 58948 KB Output is correct
25 Correct 129 ms 59340 KB Output is correct
26 Correct 111 ms 59440 KB Output is correct
27 Correct 176 ms 59952 KB Output is correct
28 Correct 192 ms 61276 KB Output is correct
29 Correct 50 ms 54340 KB Output is correct
30 Correct 44 ms 54468 KB Output is correct
31 Correct 40 ms 54540 KB Output is correct
32 Correct 37 ms 54620 KB Output is correct
33 Correct 511 ms 77896 KB Output is correct
34 Correct 796 ms 92000 KB Output is correct
35 Correct 1134 ms 103172 KB Output is correct
36 Correct 1607 ms 122156 KB Output is correct
37 Correct 1000 ms 92608 KB Output is correct
38 Correct 1111 ms 104424 KB Output is correct
39 Correct 992 ms 92736 KB Output is correct
40 Correct 1091 ms 104520 KB Output is correct
41 Correct 1027 ms 92724 KB Output is correct
42 Correct 1079 ms 104436 KB Output is correct
43 Correct 196 ms 59924 KB Output is correct
44 Correct 191 ms 61476 KB Output is correct
45 Correct 294 ms 75004 KB Output is correct
46 Correct 375 ms 74248 KB Output is correct
47 Correct 695 ms 80888 KB Output is correct
48 Correct 1121 ms 101312 KB Output is correct
49 Correct 125 ms 59668 KB Output is correct
50 Correct 121 ms 59616 KB Output is correct
51 Correct 126 ms 59836 KB Output is correct
52 Correct 129 ms 59692 KB Output is correct
53 Correct 119 ms 59588 KB Output is correct
54 Correct 119 ms 59660 KB Output is correct