Submission #294423

#	Time	Username	Problem	Language	Result	Execution time	Memory
294423		Plurm	Street Lamps (APIO19_street_lamps)	C++11	100 / 100	4304 ms	246172 KiB

street_lamps

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20