Submission #406983

#	Time	Username	Problem	Language	Result	Execution time	Memory
406983		amunduzbaev	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	227 ms	78780 KiB

street_lamps

#include "bits/stdc++.h"
using namespace std;

#define int long long
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define pii pair<int, int>

const int N = 105;
const int M = 3e5+5;
const int mod = 1e9+7;

int n, m, k, a[M];
int rr[N][N];
vector<int> in[M], qq[M];
int tree[3*M], p[3*M];

void push(int x, int lx, int rx){
	if(lx == rx || !p[x]) return;
	int m = (lx + rx)>>1;
	tree[x<<1] += (m - lx + 1) * p[x], p[x<<1] += p[x];
	tree[x<<1|1] += (rx - m) * p[x], p[x<<1|1] += p[x];
	p[x] = 0;
}

void sett(int l, int r, int v, int lx = 0, int rx = M, int x = 1){
	push(x, lx, rx);
	if(lx > r || rx < l) return;
	if(lx >= l && rx <= r){
		tree[x] += (rx - lx + 1) * v;
		p[x] += v; return;
	} int m = (lx + rx)>>1;
	sett(l, r, v, lx, m, x<<1), sett(l, r, v, m+1, rx, x<<1|1);
}

int find(int l, int r, int lx = 0, int rx = M, int x = 1){
	push(x, lx, rx);
	if(lx > r || rx < l) return 0;
	if(lx >= l && rx <= r) return tree[x];
	int m = (lx + rx)>>1;
	return find(l, r, lx, m, x<<1) + find(l, r, m+1, rx, x<<1|1);
}

/*

5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6

*/

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin>>n>>m;
	string s; cin>>s;
	
	for(int i=0;i<n;i++) a[i] = s[i] - '0';
	if(n <= 100 && m <= 100) {
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				int l = j;
				while(l < n && a[l]) rr[j][l]++, l++;
			} cin>>s;
			if(s == "query"){
				int a, b; cin>>a>>b, a--, b-=2;
				cout<<rr[a][b]<<"\n";
			} else {
				int in; cin>>in, in--;
				a[in] ^= 1;
			}
		} return 0; 
	} 
	
	vector<pair<int, int>> tt;
	bool ok = 1;
	
	for(int i=0;i<m;i++){
		string s; cin>>s;
		int a, b, in;
		if(s == "query") cin>>a>>b, --b, tt.pb({a-1, b-1}), ok &= (a == b);
		else cin>>in, tt.pb({-1, --in});
	} 

/*

5 7
11011
query 1 2
query 1 2
query 5 6
query 3 4
toggle 3
query 3 4
query 5 6

*/
	
	if(ok){
		vector<int> rr(m);
		for(int i=0;i<n;i++) if(a[i]) in[i].pb(0);
		for(int i=0;i<sz(tt);i++){
			if(tt[i].ff == -1) in[tt[i].ss].pb(i+1);
			else qq[tt[i].ff].pb(i);
		}
		for(int i=0;i<n;i++){
			if(sz(in[i]) & 1) in[i].pb(m);
			for(int j=0;j<sz(in[i]);j+=2) sett(in[i][j], in[i][j+1], 1);
			for(auto x : qq[i]) rr[x] = find(0, x);
			for(int j=0;j<sz(in[i]);j+=2) sett(in[i][j], in[i][j+1], -1);
		}
		for(int i=0;i<m;i++){
			if(~tt[i].ff) cout<<rr[i]<<"\n";
		} cout<<"\n"; 
		return 0;
	} else {
		
	}
	return 0;
}

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