oj.uz

Submission #294402

# Submission time Handle Problem Language Result Execution time Memory
294402 2020-09-08T22:20:50 Z Plurm Street Lamps (APIO19_street_lamps) C++11
20 / 100
 5000 ms 229780 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;
int lp[300005];
int qidx;
/**
 * Returns the queries index i where i-th query is toggle something in range l, r
 * Complexity: O(log N)
 * Seems like requires a segment tree (?)
 */
int lastProcessed(int l, int r){
	// Try O(N) first
	/// @TODO: opt to O(log N)
	int mx = -2;
	for(int i = l; i <= r; i++) mx = max(mx, lp[i]);
	return mx;
}
/**
 * Find rightmost i such that state[i] == 0 but i < x or returns 0 if not exists
 * Complexity: O(log N)
 * Requires descent on fenwick tree
 */
int getRightmostZero(int x){
	// Try O(N) first
	/// @TODO: opt to O(log N)
	for(int i = x-1; i > 0; i--){
		if(state[i] == '0') return i;
	}
	return 0;
}
/**
 * Find leftmost i such that state[i] == 0 but i > x or returns n+1 if not exists
 * Complexity: O(log N)
 * Requires descent on fenwick tree
 */
int getLeftmostZero(int x){
	// Try O(N) first
	/// @TODO: opt to O(log N)
	for(int i = x+1; i <= n; i++){
		if(state[i] == '0') return i;
	}
	return n+1;
}
/**
 * Returns whether there are some zeroes in the range l, r ?
 * Complexity: O(log N)
 * Requires another fenwick tree
 */
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,
		// printf("DBG %d %d %d\n", sum(l,r), qidx, lastProcessed(l, r));
		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);
		// printf("Added %d (%d - %d) to (%d, %d), (%d, %d)\n",d,qidx,lastProcessed(l,r),l+1,1,n,r-1);
		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);
	}
	for(int j = l+1; j < r; j++) lp[j] = qidx;
	state[i] = '0'+'1'-state[i];
}
int main(){
	int q;
	scanf("%d%d",&n,&q);
	for(int i = 0; i <= n+1; i++) lp[i] = -1;
	scanf("%s", state+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:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:135:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  135 |  scanf("%s", state+1);
      |  ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  139 |   scanf("%s%d",str,&l);
      |   ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:140:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  140 |   if(str[0] == 'q') scanf("%d",&r);
      |                     ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 37748 KB Output is correct
2 Correct 234 ms 38308 KB Output is correct
3 Correct 414 ms 40084 KB Output is correct
4 Correct 1696 ms 144984 KB Output is correct
5 Correct 1930 ms 153892 KB Output is correct
6 Correct 1490 ms 135820 KB Output is correct
7 Correct 2340 ms 183356 KB Output is correct
8 Execution timed out 5033 ms 182936 KB Time limit exceeded

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28672 KB Output is correct
2 Correct 21 ms 28800 KB Output is correct
3 Correct 23 ms 28800 KB Output is correct
4 Correct 22 ms 28928 KB Output is correct
5 Correct 792 ms 86132 KB Output is correct
6 Correct 1738 ms 128860 KB Output is correct
7 Correct 2649 ms 172536 KB Output is correct
8 Execution timed out 5041 ms 229376 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28928 KB Output is correct
2 Correct 25 ms 28800 KB Output is correct
3 Correct 22 ms 28800 KB Output is correct
4 Correct 23 ms 28672 KB Output is correct
5 Correct 3585 ms 227972 KB Output is correct
6 Correct 2699 ms 186596 KB Output is correct
7 Correct 1784 ms 143596 KB Output is correct
8 Correct 663 ms 86320 KB Output is correct
9 Correct 316 ms 40420 KB Output is correct
10 Correct 183 ms 37476 KB Output is correct
11 Correct 328 ms 40420 KB Output is correct
12 Correct 191 ms 37480 KB Output is correct
13 Correct 314 ms 40416 KB Output is correct
14 Correct 182 ms 37476 KB Output is correct
15 Correct 3501 ms 229780 KB Output is correct
16 Execution timed out 5024 ms 229020 KB Time limit exceeded

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28536 KB Output is correct
2 Correct 21 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 21 ms 28544 KB Output is correct
5 Correct 21 ms 28544 KB Output is correct
6 Correct 20 ms 28544 KB Output is correct
7 Correct 20 ms 28544 KB Output is correct
8 Correct 195 ms 37748 KB Output is correct
9 Correct 234 ms 38308 KB Output is correct
10 Correct 414 ms 40084 KB Output is correct
11 Correct 1696 ms 144984 KB Output is correct
12 Correct 1930 ms 153892 KB Output is correct
13 Correct 1490 ms 135820 KB Output is correct
14 Correct 2340 ms 183356 KB Output is correct
15 Execution timed out 5033 ms 182936 KB Time limit exceeded