oj.uz

Submission #407140

# Submission time Handle Problem Language Result Execution time Memory
407140 2021-05-18T14:48:18 Z amunduzbaev Street Lamps (APIO19_street_lamps) C++14
100 / 100
 3536 ms 60168 KB 
#include "bits/stdc++.h"
using namespace std;

#define int long long
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define pii pair<int, int>
#define lb lower_bound
#define ub upper_bound

const int N = 3e5+5;
const int mod = 1e9+7;

int n, m, k, a[N], rr, cnt;
vector<array<int, 3>> tree[4*N];
string s;

void find(int a, int b, int lx = 1, int rx = n, int x = 1){
	for(auto x : tree[x]){
		if(x[0] <= b && b <= x[1]) rr += x[2], cnt++;
	} int m = (lx + rx)>>1;
	if(lx == rx) return;
	if(a <= m) find(a, b, lx, m, x<<1);
	else find(a, b, m+1, rx, x<<1|1);
}

void add(int l, int r, array<int, 3> v, int lx = 1, int rx = n, int x = 1){
	if(lx > r || rx < l) return;
	if(lx >= l && rx <= r) { tree[x].pb(v); return; }
	int m = (lx + rx)>>1;
	add(l, r, v, lx, m, x<<1), add(l, r, v, m+1, rx, x<<1|1);
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m>>s;
	
	set<int> ss;
	s = "$" + s;
	for(int i=1;i<=n;i++) {
		a[i] = s[i] - '0';
		if(!a[i]) ss.insert(i);
	} 
	
	for(int i=1;i<=n;i++){
		if(!a[i]) continue;
		int j = i;
		while(j <= n && a[j] == a[i]) j++;
		j--, add(i, j, {i, j, 0}), i = j;
	}
	
	for(int i=1;i<=m;i++){
		cin>>s;
		if(s == "query"){
			int a, b; cin>>a>>b, b--; 
			rr = 0, cnt = 0, find(a, b);
			if(cnt & 1) rr += i;
			cout<<rr<<"\n";
		} else {
			int m; cin>>m;
			if(a[m]){
				auto lx = ss.lb(m);
				auto rx = ss.ub(m);
				int r = (lx == ss.end() ? n + 1 : *lx);	
				int l = (rx == ss.begin() ? 0 : *--rx);
				add(l+1, m, {m, r-1, i}), ss.insert(m);
			} else {
				ss.erase(m);
				auto lx = ss.lb(m);
				auto rx = ss.ub(m);
				int r = (lx == ss.end() ? n + 1 : *lx);	
				int l = (rx == ss.begin() ? 0 : *--rx);
				add(l+1, m, {m, r-1, -i});
			} a[m] ^= 1;
		}
	} return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28492 KB Output is correct
2 Correct 15 ms 28472 KB Output is correct
3 Correct 15 ms 28492 KB Output is correct
4 Correct 16 ms 28508 KB Output is correct
5 Correct 15 ms 28408 KB Output is correct
6 Correct 16 ms 28492 KB Output is correct
7 Correct 16 ms 28456 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 914 ms 36824 KB Output is correct
2 Correct 455 ms 40284 KB Output is correct
3 Correct 249 ms 42308 KB Output is correct
4 Correct 557 ms 54552 KB Output is correct
5 Correct 467 ms 52420 KB Output is correct
6 Correct 506 ms 55724 KB Output is correct
7 Correct 279 ms 51740 KB Output is correct
8 Correct 214 ms 39188 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28540 KB Output is correct
2 Correct 18 ms 28492 KB Output is correct
3 Correct 18 ms 28492 KB Output is correct
4 Correct 18 ms 28464 KB Output is correct
5 Correct 803 ms 56468 KB Output is correct
6 Correct 617 ms 55056 KB Output is correct
7 Correct 546 ms 51608 KB Output is correct
8 Correct 247 ms 39084 KB Output is correct
9 Correct 141 ms 32104 KB Output is correct
10 Correct 154 ms 32368 KB Output is correct
11 Correct 152 ms 32560 KB Output is correct
12 Correct 338 ms 51752 KB Output is correct
13 Correct 275 ms 39096 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28488 KB Output is correct
2 Correct 22 ms 28504 KB Output is correct
3 Correct 23 ms 28492 KB Output is correct
4 Correct 20 ms 28528 KB Output is correct
5 Correct 339 ms 48152 KB Output is correct
6 Correct 512 ms 51744 KB Output is correct
7 Correct 607 ms 55376 KB Output is correct
8 Correct 786 ms 60168 KB Output is correct
9 Correct 390 ms 43928 KB Output is correct
10 Correct 225 ms 45808 KB Output is correct
11 Correct 379 ms 44064 KB Output is correct
12 Correct 232 ms 45492 KB Output is correct
13 Correct 348 ms 43412 KB Output is correct
14 Correct 228 ms 45636 KB Output is correct
15 Correct 333 ms 51756 KB Output is correct
16 Correct 248 ms 39112 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28492 KB Output is correct
2 Correct 15 ms 28472 KB Output is correct
3 Correct 15 ms 28492 KB Output is correct
4 Correct 16 ms 28508 KB Output is correct
5 Correct 15 ms 28408 KB Output is correct
6 Correct 16 ms 28492 KB Output is correct
7 Correct 16 ms 28456 KB Output is correct
8 Correct 914 ms 36824 KB Output is correct
9 Correct 455 ms 40284 KB Output is correct
10 Correct 249 ms 42308 KB Output is correct
11 Correct 557 ms 54552 KB Output is correct
12 Correct 467 ms 52420 KB Output is correct
13 Correct 506 ms 55724 KB Output is correct
14 Correct 279 ms 51740 KB Output is correct
15 Correct 214 ms 39188 KB Output is correct
16 Correct 18 ms 28540 KB Output is correct
17 Correct 18 ms 28492 KB Output is correct
18 Correct 18 ms 28492 KB Output is correct
19 Correct 18 ms 28464 KB Output is correct
20 Correct 803 ms 56468 KB Output is correct
21 Correct 617 ms 55056 KB Output is correct
22 Correct 546 ms 51608 KB Output is correct
23 Correct 247 ms 39084 KB Output is correct
24 Correct 141 ms 32104 KB Output is correct
25 Correct 154 ms 32368 KB Output is correct
26 Correct 152 ms 32560 KB Output is correct
27 Correct 338 ms 51752 KB Output is correct
28 Correct 275 ms 39096 KB Output is correct
29 Correct 21 ms 28488 KB Output is correct
30 Correct 22 ms 28504 KB Output is correct
31 Correct 23 ms 28492 KB Output is correct
32 Correct 20 ms 28528 KB Output is correct
33 Correct 339 ms 48152 KB Output is correct
34 Correct 512 ms 51744 KB Output is correct
35 Correct 607 ms 55376 KB Output is correct
36 Correct 786 ms 60168 KB Output is correct
37 Correct 390 ms 43928 KB Output is correct
38 Correct 225 ms 45808 KB Output is correct
39 Correct 379 ms 44064 KB Output is correct
40 Correct 232 ms 45492 KB Output is correct
41 Correct 348 ms 43412 KB Output is correct
42 Correct 228 ms 45636 KB Output is correct
43 Correct 333 ms 51756 KB Output is correct
44 Correct 248 ms 39112 KB Output is correct
45 Correct 3536 ms 34932 KB Output is correct
46 Correct 293 ms 35396 KB Output is correct
47 Correct 289 ms 41104 KB Output is correct
48 Correct 556 ms 54100 KB Output is correct
49 Correct 140 ms 32600 KB Output is correct
50 Correct 132 ms 32524 KB Output is correct
51 Correct 133 ms 32836 KB Output is correct
52 Correct 133 ms 33012 KB Output is correct
53 Correct 132 ms 33056 KB Output is correct
54 Correct 130 ms 33092 KB Output is correct