oj.uz

Submission #253551

# Submission time Handle Problem Language Result Execution time Memory
253551 2020-07-28T08:49:04 Z Saboon Street Lamps (APIO19_street_lamps) C++14
100 / 100
 3586 ms 119820 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 20;

int n;
set<int> zi;
vector<int> fenidx[maxn], fen[maxn];
int Q1[maxn], Q2[maxn];
string type[maxn];

int get(int x, int y){
	int ret = 0;
	for (int i = x; i; i -= i & -i)
		for (int j = lower_bound(fenidx[i].begin(),fenidx[i].end(),y)-fenidx[i].begin()+1; j; j -= j & -j)
			ret += fen[i][j-1];
	return ret;
}

void add(int x, int y, int val){
	for (int i = x; i < maxn; i += i & -i)
		for (int j = lower_bound(fenidx[i].begin(),fenidx[i].end(),y)-fenidx[i].begin()+1; j <= fen[i].size(); j += j & -j)
			fen[i][j-1] += val;
}

void getinit(int x, int y){
	for (int i = x; i; i -= i & -i)
		fenidx[i].push_back(y);
}
void addinit(int x, int y){
	for (int i = x; i < maxn; i += i & -i)
		fenidx[i].push_back(y);
}
int getnex(int idx){
	auto it = zi.lower_bound(idx);
	return it == zi.end() ? n+1 : *it;
}
int getpre(int idx){
	auto it = zi.lower_bound(idx);
	if (it == zi.begin())
		return 1;
	it --;
	return it == zi.end() ? 1 : *it + 1;
}

int main(){
	ios_base::sync_with_stdio(false);
	int q;
	string s;
	cin >> n >> q >> s;
	for (int i = 1; i <= n; i++)
		if (s[i-1] == '0')
			zi.insert(i);
	string copys = s;
	for (int i = 1; i <= q; i++){
		cin >> type[i];
		if (type[i] == "toggle"){
			int now = Q1[i];
			cin >> Q1[i];
			if (s[now-1] == '1'){
				int pre = getpre(Q1[i]), now = Q1[i], nex = getnex(Q1[i]+1);
				addinit(pre, now+1), addinit(pre, nex+1), addinit(now+1, now+1), addinit(now+1, nex+1), s[now-1] = '0';
				zi.insert(now);
			}
			else{
				int pre = getpre(Q1[i]), now = Q1[i], nex = getnex(Q1[i]+1);
				addinit(pre, now+1), addinit(pre, nex+1), addinit(now+1, now+1), addinit(now+1, nex+1), s[now-1] = '1';
				zi.erase(now);
			}
		}
		else{
			cin >> Q1[i] >> Q2[i];
			getinit(Q1[i], Q2[i]);
		}
	}
	s = copys;
	zi.clear();
	for (int i = 1; i <= n; i++)
		if (s[i-1] == '0')
			zi.insert(i);
	for (int i = 1; i < maxn; i++){
		sort(fenidx[i].begin(), fenidx[i].end());
		fenidx[i].resize(unique(fenidx[i].begin(),fenidx[i].end())-fenidx[i].begin());
		fen[i].resize(fenidx[i].size());
	}
	for (int i = 1; i <= q; i++){
		if (type[i] == "toggle"){
			int now = Q1[i];
			if (s[now-1] == '1'){
				int pre = getpre(Q1[i]), now = Q1[i], nex = getnex(Q1[i]+1);
				add(pre, now+1, +i), add(pre, nex+1, -i), add(now+1, now+1, -i), add(now+1, nex+1, +i), s[now-1] = '0';
				zi.insert(now);
			}
			else{
				int pre = getpre(Q1[i]), now = Q1[i], nex = getnex(Q1[i]+1);
				add(pre, now+1, -i), add(pre, nex+1, +i), add(now+1, now+1, +i), add(now+1, nex+1, -i), s[now-1] = '1';
				zi.erase(now);
			}
		}
		else{
			cin >> Q1[i] >> Q2[i];
			int k = getnex(Q1[i]);
			if (k < Q2[i])
				cout << get(Q1[i], Q2[i]) << '\n';
			else
				cout << i + get(Q1[i], Q2[i]) << '\n';
		}
	}
}

Compilation message

street_lamps.cpp: In function 'void add(int, int, int)':
street_lamps.cpp:22:88: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = lower_bound(fenidx[i].begin(),fenidx[i].end(),y)-fenidx[i].begin()+1; j <= fen[i].size(); j += j & -j)
                                                                                      ~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 13 ms 23904 KB Output is correct
3 Correct 13 ms 23908 KB Output is correct
4 Correct 14 ms 23832 KB Output is correct
5 Correct 14 ms 23808 KB Output is correct
6 Correct 14 ms 23808 KB Output is correct
7 Correct 13 ms 23808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 72560 KB Output is correct
2 Correct 946 ms 74700 KB Output is correct
3 Correct 1329 ms 72792 KB Output is correct
4 Correct 2389 ms 93748 KB Output is correct
5 Correct 2119 ms 88704 KB Output is correct
6 Correct 2603 ms 96232 KB Output is correct
7 Correct 1505 ms 72576 KB Output is correct
8 Correct 923 ms 59908 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24192 KB Output is correct
2 Correct 18 ms 24192 KB Output is correct
3 Correct 16 ms 24064 KB Output is correct
4 Correct 17 ms 24064 KB Output is correct
5 Correct 3581 ms 119820 KB Output is correct
6 Correct 2898 ms 103184 KB Output is correct
7 Correct 2207 ms 85976 KB Output is correct
8 Correct 930 ms 60548 KB Output is correct
9 Correct 153 ms 30508 KB Output is correct
10 Correct 164 ms 30916 KB Output is correct
11 Correct 171 ms 31076 KB Output is correct
12 Correct 1484 ms 73008 KB Output is correct
13 Correct 1128 ms 60504 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23936 KB Output is correct
2 Correct 17 ms 24112 KB Output is correct
3 Correct 18 ms 24192 KB Output is correct
4 Correct 20 ms 24192 KB Output is correct
5 Correct 1254 ms 72168 KB Output is correct
6 Correct 1784 ms 87928 KB Output is correct
7 Correct 2554 ms 100824 KB Output is correct
8 Correct 3586 ms 113688 KB Output is correct
9 Correct 1322 ms 93776 KB Output is correct
10 Correct 1416 ms 112460 KB Output is correct
11 Correct 1298 ms 93784 KB Output is correct
12 Correct 1413 ms 112688 KB Output is correct
13 Correct 1282 ms 93808 KB Output is correct
14 Correct 1415 ms 112548 KB Output is correct
15 Correct 1655 ms 78980 KB Output is correct
16 Correct 1082 ms 66052 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 13 ms 23904 KB Output is correct
3 Correct 13 ms 23908 KB Output is correct
4 Correct 14 ms 23832 KB Output is correct
5 Correct 14 ms 23808 KB Output is correct
6 Correct 14 ms 23808 KB Output is correct
7 Correct 13 ms 23808 KB Output is correct
8 Correct 851 ms 72560 KB Output is correct
9 Correct 946 ms 74700 KB Output is correct
10 Correct 1329 ms 72792 KB Output is correct
11 Correct 2389 ms 93748 KB Output is correct
12 Correct 2119 ms 88704 KB Output is correct
13 Correct 2603 ms 96232 KB Output is correct
14 Correct 1505 ms 72576 KB Output is correct
15 Correct 923 ms 59908 KB Output is correct
16 Correct 20 ms 24192 KB Output is correct
17 Correct 18 ms 24192 KB Output is correct
18 Correct 16 ms 24064 KB Output is correct
19 Correct 17 ms 24064 KB Output is correct
20 Correct 3581 ms 119820 KB Output is correct
21 Correct 2898 ms 103184 KB Output is correct
22 Correct 2207 ms 85976 KB Output is correct
23 Correct 930 ms 60548 KB Output is correct
24 Correct 153 ms 30508 KB Output is correct
25 Correct 164 ms 30916 KB Output is correct
26 Correct 171 ms 31076 KB Output is correct
27 Correct 1484 ms 73008 KB Output is correct
28 Correct 1128 ms 60504 KB Output is correct
29 Correct 15 ms 23936 KB Output is correct
30 Correct 17 ms 24112 KB Output is correct
31 Correct 18 ms 24192 KB Output is correct
32 Correct 20 ms 24192 KB Output is correct
33 Correct 1254 ms 72168 KB Output is correct
34 Correct 1784 ms 87928 KB Output is correct
35 Correct 2554 ms 100824 KB Output is correct
36 Correct 3586 ms 113688 KB Output is correct
37 Correct 1322 ms 93776 KB Output is correct
38 Correct 1416 ms 112460 KB Output is correct
39 Correct 1298 ms 93784 KB Output is correct
40 Correct 1413 ms 112688 KB Output is correct
41 Correct 1282 ms 93808 KB Output is correct
42 Correct 1415 ms 112548 KB Output is correct
43 Correct 1655 ms 78980 KB Output is correct
44 Correct 1082 ms 66052 KB Output is correct
45 Correct 415 ms 57472 KB Output is correct
46 Correct 554 ms 57172 KB Output is correct
47 Correct 1516 ms 67256 KB Output is correct
48 Correct 2636 ms 97900 KB Output is correct
49 Correct 201 ms 34668 KB Output is correct
50 Correct 200 ms 34532 KB Output is correct
51 Correct 210 ms 35148 KB Output is correct
52 Correct 233 ms 36968 KB Output is correct
53 Correct 252 ms 36864 KB Output is correct
54 Correct 230 ms 36840 KB Output is correct