oj.uz

Submission #294423

# Submission time Handle Problem Language Result Execution time Memory
294423 2020-09-08T22:43:40 Z Plurm Street Lamps (APIO19_street_lamps) C++11
100 / 100
 4304 ms 246172 KB 
#include <bits/stdc++.h>
using namespace std;
int n;
char state[300005];
set<int> setBlock[300005];
vector<int> vectorBlock[300005];
vector<int> FT[300005];
/**
 * Build the (compressed) fenwick tree
 */
void build(int l, int r){
	for(int i = l; i > 0; i -= i & -i){
		setBlock[i].insert(r);
	}
}
void finalizeBuild(int n){
	for(int i = 1; i <= n; i++){
		setBlock[i].insert(1);
		setBlock[i].insert(n);
		for(int x : setBlock[i]){
			vectorBlock[i].push_back(x);
			FT[i].push_back(0);
		}
		FT[i].push_back(0);
	}
}
void add(int l, int r, int x){
	for(int i = l; i <= n; i += i & -i){
		int st = lower_bound(vectorBlock[i].begin(), vectorBlock[i].end(), r) - vectorBlock[i].begin() + 1;
		for(int j = st; j <= vectorBlock[i].size(); j += j & -j){
			FT[i][j] += x;
		}
	}
}
int sum(int l, int r){
	int ret = 0;
	for(int i = l; i > 0; i -= i & -i){
		int st = lower_bound(vectorBlock[i].begin(), vectorBlock[i].end(), r) - vectorBlock[i].begin() + 1;
		assert(vectorBlock[i][st-1] == r);
		for(int j = st; j > 0; j -= j & -j){
			ret += FT[i][j];
		}
	}
	return ret;
}
vector<tuple<char,int,int> > queries;

// Helpers
int seg[1048576];
int lb[1048576];
int rb[1048576];
int lazy[1048576];
void hBuild(int c, int l, int r){
	lb[c] = l;
	rb[c] = r;
	seg[c] = -1;
	lazy[c] = -1;
	if(l == r) return;
	int k = (l+r)/2;
	hBuild(2*c, l, k);
	hBuild(2*c+1, k+1, r);
}
void hProp(int c){
	if(lazy[c] != -1){
		seg[c] = max(seg[c], lazy[c]);
		if(lb[c] != rb[c]){
			lazy[2*c] = max(lazy[2*c], lazy[c]);
			lazy[2*c+1] = max(lazy[2*c+1], lazy[c]);
		}
		lazy[c] = -1;
	}
}
void hUpdate(int c, int l, int r, int x){
	if(l > r) return;
	if(lb[c] == l && rb[c] == r) lazy[c] = max(lazy[c], x);
	hProp(c);
	if(lb[c] == l && rb[c] == r) return;
	int k = (lb[c] + rb[c])/2;
	if(l <= k && k < r){
		hUpdate(2*c, l, k, x);
		hUpdate(2*c+1, k+1, r, x);
	}else if(r <= k){
		hUpdate(2*c, l, r, x);
		hProp(2*c+1);
	}else{
		hProp(2*c);
		hUpdate(2*c+1, l, r, x);
	}
	seg[c] = max(seg[2*c], seg[2*c+1]);
}
int hQuery(int c, int l, int r){
	hProp(c);
	if(lb[c] == l && rb[c] == r) return seg[c];
	int k = (lb[c] + rb[c])/2;
	if(l <= k && k < r){
		return max(hQuery(2*c, l, k), hQuery(2*c+1, k+1, r));
	}else if(r <= k){
		return hQuery(2*c, l, r);
	}else{
		return hQuery(2*c+1, l, r);
	}
}
int qidx;
int hFT[300005];
void hAdd(int idx, int amt){
	while(idx <= n+1){
		hFT[idx] += amt;
		idx += idx & -idx;
	}
}
int hSum(int idx){
	int ret = 0;
	while(idx > 0){
		ret += hFT[idx];
		idx -= idx & -idx;
	}
	return ret;
}

/**
 * Returns the queries index i where i-th query is toggle something in range l, r
 * Complexity: O(log N)
 * Uses a max-lazy segment tree
 */
int lastProcessed(int l, int r){
	return hQuery(1, l, r);
}
/**
 * Find rightmost i such that state[i] == 0 but i < x or returns 0 if not exists
 * Complexity: O(log^2 N)
 * Binary search on fenwick tree
 */
int getRightmostZero(int x){
	int lo = 0;
	int hi = x-1;
	int s = hSum(x-1);
	while(lo < hi){
		int mid = (lo+hi+1)/2;
		if(hSum(mid-1) == s){
			hi = mid-1;
		}else{
			lo = mid;
		}
	}
	return lo;
}
/**
 * Find leftmost i such that state[i] == 0 but i > x or returns n+1 if not exists
 * Complexity: O(log^2 N)
 * Binary search on fenwick tree
 */
int getLeftmostZero(int x){
	int lo = x+1;
	int hi = n+1;
	int s = hSum(x);
	while(lo < hi){
		int mid = (lo+hi)/2;
		if(hSum(mid) == s){
			lo = mid+1;
		}else{
			hi = mid;
		}
	}
	return lo;
}
/**
 * Returns whether there are some zeroes in the range l, r ?
 * Complexity: O(log^2 N)
 */
bool hasZero(int l, int r){
	return getLeftmostZero(l-1) <= r;
}
int query(int l, int r){
	if(!hasZero(l, r)){
		// if all l -- r is 1,
		return sum(l,r) + qidx - lastProcessed(l, r);
	}else{
		// elif some l -- r is 0
		return sum(l,r);
	}
}
void toggle(int i){
	int l = getRightmostZero(i);
	int r = getLeftmostZero(i);
	if(state[i] == '1'){
		// toggle 1 to 0: find rightmost left 0, leftmost right 0
		// let them be l, r
		// (all subintervals) stats[l+1][r-1] += i - lastProcessed(l, r)
		int d = qidx - lastProcessed(l, r);
		add(l+1, 1, d);
		add(l+1, r, -d);
	}else{
		// toggle 0 to 1: find rightmost left 0, leftmost right 0
		// let them be l, r
		// (all subintervals) stats[l+1][i-1] += i - lastProcessed(l, i)
		// (all subintervals) stats[i+1][r-1] += i - lastProcessed(i, r)
		int dl = qidx - lastProcessed(l, i);
		add(l+1, 1, dl);
		add(l+1, i, -dl);
		int dr = qidx - lastProcessed(i, r);
		add(i+1, 1, dr);
		add(i+1, r, -dr);
	}
	hUpdate(1, l+1, r-1, qidx);
	if(state[i] == '0') hAdd(i, -1);
	else hAdd(i, 1);
	state[i] = '0'+'1'-state[i];
}
int main(){
	int q;
	scanf("%d%d",&n,&q);
	hBuild(1, 0, n+1);
	scanf("%s", state+1);
	for(int i = 1; i <= n; i++){
		if(state[i] == '0') hAdd(i, 1);
	}
	for(int i = 0; i < q; i++){
		char str[32];
		int l, r = 0;
		scanf("%s%d",str,&l);
		if(str[0] == 'q') scanf("%d",&r);
		r--;
		queries.emplace_back(str[0], l, r);
		if(str[0] == 'q') build(l, r);
	}
	finalizeBuild(n);
	for(qidx = 0; qidx < q; qidx++){
		char c; int l, r;
		tie(c, l, r) = queries[qidx];
		if(c == 'q'){
			printf("%d\n", query(l, r));
		}else{
			toggle(l);
		}
	}
}

Compilation message

street_lamps.cpp: In function 'void add(int, int, int)':
street_lamps.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int j = st; j <= vectorBlock[i].size(); j += j & -j){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:211:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  211 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:213:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  213 |  scanf("%s", state+1);
      |  ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:220:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  220 |   scanf("%s%d",str,&l);
      |   ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:221:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  221 |   if(str[0] == 'q') scanf("%d",&r);
      |                     ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28544 KB Output is correct
2 Correct 20 ms 28544 KB Output is correct
3 Correct 21 ms 28544 KB Output is correct
4 Correct 21 ms 28544 KB Output is correct
5 Correct 19 ms 28544 KB Output is correct
6 Correct 21 ms 28544 KB Output is correct
7 Correct 22 ms 28544 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 35052 KB Output is correct
2 Correct 355 ms 38264 KB Output is correct
3 Correct 605 ms 40100 KB Output is correct
4 Correct 2468 ms 160452 KB Output is correct
5 Correct 2867 ms 169096 KB Output is correct
6 Correct 2412 ms 151136 KB Output is correct
7 Correct 2526 ms 198144 KB Output is correct
8 Correct 2888 ms 197840 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28800 KB Output is correct
2 Correct 22 ms 28800 KB Output is correct
3 Correct 21 ms 28928 KB Output is correct
4 Correct 22 ms 29056 KB Output is correct
5 Correct 1778 ms 102408 KB Output is correct
6 Correct 2507 ms 144876 KB Output is correct
7 Correct 3148 ms 187864 KB Output is correct
8 Correct 4304 ms 244340 KB Output is correct
9 Correct 209 ms 35496 KB Output is correct
10 Correct 240 ms 38308 KB Output is correct
11 Correct 234 ms 38436 KB Output is correct
12 Correct 3708 ms 245836 KB Output is correct
13 Correct 4289 ms 246172 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28928 KB Output is correct
2 Correct 20 ms 28920 KB Output is correct
3 Correct 21 ms 28792 KB Output is correct
4 Correct 19 ms 28800 KB Output is correct
5 Correct 3692 ms 239612 KB Output is correct
6 Correct 3127 ms 202020 KB Output is correct
7 Correct 2519 ms 159760 KB Output is correct
8 Correct 1587 ms 102744 KB Output is correct
9 Correct 443 ms 40420 KB Output is correct
10 Correct 304 ms 37476 KB Output is correct
11 Correct 438 ms 40420 KB Output is correct
12 Correct 304 ms 37476 KB Output is correct
13 Correct 443 ms 40452 KB Output is correct
14 Correct 325 ms 37472 KB Output is correct
15 Correct 3685 ms 243580 KB Output is correct
16 Correct 4130 ms 243128 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28544 KB Output is correct
2 Correct 20 ms 28544 KB Output is correct
3 Correct 21 ms 28544 KB Output is correct
4 Correct 21 ms 28544 KB Output is correct
5 Correct 19 ms 28544 KB Output is correct
6 Correct 21 ms 28544 KB Output is correct
7 Correct 22 ms 28544 KB Output is correct
8 Correct 283 ms 35052 KB Output is correct
9 Correct 355 ms 38264 KB Output is correct
10 Correct 605 ms 40100 KB Output is correct
11 Correct 2468 ms 160452 KB Output is correct
12 Correct 2867 ms 169096 KB Output is correct
13 Correct 2412 ms 151136 KB Output is correct
14 Correct 2526 ms 198144 KB Output is correct
15 Correct 2888 ms 197840 KB Output is correct
16 Correct 22 ms 28800 KB Output is correct
17 Correct 22 ms 28800 KB Output is correct
18 Correct 21 ms 28928 KB Output is correct
19 Correct 22 ms 29056 KB Output is correct
20 Correct 1778 ms 102408 KB Output is correct
21 Correct 2507 ms 144876 KB Output is correct
22 Correct 3148 ms 187864 KB Output is correct
23 Correct 4304 ms 244340 KB Output is correct
24 Correct 209 ms 35496 KB Output is correct
25 Correct 240 ms 38308 KB Output is correct
26 Correct 234 ms 38436 KB Output is correct
27 Correct 3708 ms 245836 KB Output is correct
28 Correct 4289 ms 246172 KB Output is correct
29 Correct 22 ms 28928 KB Output is correct
30 Correct 20 ms 28920 KB Output is correct
31 Correct 21 ms 28792 KB Output is correct
32 Correct 19 ms 28800 KB Output is correct
33 Correct 3692 ms 239612 KB Output is correct
34 Correct 3127 ms 202020 KB Output is correct
35 Correct 2519 ms 159760 KB Output is correct
36 Correct 1587 ms 102744 KB Output is correct
37 Correct 443 ms 40420 KB Output is correct
38 Correct 304 ms 37476 KB Output is correct
39 Correct 438 ms 40420 KB Output is correct
40 Correct 304 ms 37476 KB Output is correct
41 Correct 443 ms 40452 KB Output is correct
42 Correct 325 ms 37472 KB Output is correct
43 Correct 3685 ms 243580 KB Output is correct
44 Correct 4130 ms 243128 KB Output is correct
45 Correct 137 ms 33384 KB Output is correct
46 Correct 218 ms 33580 KB Output is correct
47 Correct 1397 ms 97568 KB Output is correct
48 Correct 2678 ms 173988 KB Output is correct
49 Correct 233 ms 38308 KB Output is correct
50 Correct 235 ms 38304 KB Output is correct
51 Correct 243 ms 38744 KB Output is correct
52 Correct 310 ms 44324 KB Output is correct
53 Correct 304 ms 44460 KB Output is correct
54 Correct 299 ms 44320 KB Output is correct