Submission #471124

#	Time	Username	Problem	Language	Result	Execution time	Memory
471124		keta_tsimakuridze	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	674 ms	58180 KiB

street_lamps

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 3e5 + 5, mod = 1e9 + 7; // !
int t, tree[4 * N],Q, fw[N],a[N],n,ans[N];
string s;
vector<pii> add[N],q[N];
vector<int> rem[N];
void update(int u,int ind,int l,int r) {
	if(l > ind || r < ind) return;
	if(l == r) {
		tree[u] ^= 1;
		return;
	}
	int mid = (l + r)/2;
	update(2 * u,ind,l,mid); update(2 * u + 1,ind,mid + 1, r);
	tree[u] = min(tree[2 * u], tree[2 *u + 1]);
}
int getL(int u,int ind,int l,int r) {
	if(l == r) {
		if(tree[u]) {
			return l;
		}
		return l + 1;
	}
	int mid = (l + r)/2;
	if(r <= ind) {
		if(tree[2 * u + 1] == 1) return getL(2 * u, ind, l, mid);
		return getL(2 * u + 1,ind,mid + 1, r);
	}
	if(mid >= ind) return getL(2 * u, ind, l, mid);
	int x = getL(2 * u + 1,ind,mid + 1,r);
	if(x > mid + 1) return x;
	return getL(2 * u, ind, l, mid);
}
int getR(int u,int ind,int l,int r) {
	if(l == r) {
		if(tree[u]) {
			return l;
		}
		return l - 1;
	}
	int mid = (l + r)/2;
	if(l >= ind) {
		if(tree[2 * u] == 1) return getR(2 * u + 1, ind, mid + 1,r);
		return getR(2 * u,ind, l, mid);
	}
	if(mid < ind) return getR(2 * u + 1, ind, mid + 1, r);
	int x = getR(2 * u,ind,l,mid);
	if(x < mid) return x;
	return getR(2 * u + 1, ind, mid + 1, r);
}
void upd(int ind,int val) {
	for(ind;ind >= 1; ind -= ind & (-ind)) fw[ind] += val;
}
int get(int ind) {
	int ans = 0;
	for(ind; ind <= n; ind += ind & (-ind)) ans += fw[ind];
	return ans;
}
main(){
	// All toggle events happen before all query events.
	cin >> n >> Q;
	cin >> s;
	for(int i = 1; i <= n; i++) {
		a[i] = s[i - 1] - '0';
		if(a[i]) update(1,i,1,n);
	}
	int ind = 0,start = 0;
	for(int i = 1; i <= Q; i++) {
		string s;
		
		cin >> s;
		if(s == "toggle") {
			int id;
			cin >> id;
			update(1,id,1,n);
			
			int l = getL(1,id - 1,1,n);
			int r = getR(1,id + 1,1,n);
			int f = 1;
			if(a[id] == 0) f = -1;
			a[id] ^= 1;
			add[l].push_back({r, f * i});
			if(id + 1 <= r) add[id + 1].push_back({r, f * -i});
			if(l <= id - 1) add[l].push_back({id - 1,f * -i});
		}
		else {
			int l,r;
			cin >> l >> r;
			r--;
			if(!start) start = i;
			q[l].push_back({r, i});
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < add[i].size(); j++) {
			upd(add[i][j].f,add[i][j].s);			
			rem[add[i][j].f].push_back(add[i][j].s);
		}
		for(int j = 0; j < q[i].size(); j++) {
			ans[q[i][j].s] = get(q[i][j].f);
			if(getR(1,i,1,n) >= q[i][j].f) ans[q[i][j].s] += q[i][j].s;
		}
		for(int j = 0; j < rem[i].size(); j++) {
			upd(i,-rem[i][j]);
		}
	}
	for(int i = start; i <= Q; i++) {
		cout << ans[i] <<" ";
	}
 }

Compilation message (stderr)

street_lamps.cpp: In function 'void upd(long long int, long long int)':
street_lamps.cpp:57:6: warning: statement has no effect [-Wunused-value]
   57 |  for(ind;ind >= 1; ind -= ind & (-ind)) fw[ind] += val;
      |      ^~~
street_lamps.cpp: In function 'long long int get(long long int)':
street_lamps.cpp:61:6: warning: statement has no effect [-Wunused-value]
   61 |  for(ind; ind <= n; ind += ind & (-ind)) ans += fw[ind];
      |      ^~~
street_lamps.cpp: At global scope:
street_lamps.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main(){
      | ^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:100:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int j = 0; j < add[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~
street_lamps.cpp:104:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int j = 0; j < q[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~
street_lamps.cpp:108:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   for(int j = 0; j < rem[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~
street_lamps.cpp:72:6: warning: unused variable 'ind' [-Wunused-variable]
   72 |  int ind = 0,start = 0;
      |      ^~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20