제출 #516354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
516354		CSQ31	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5057 ms	39584 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
int sq = 550;
const int MAXN = 3e5+1;
int a[MAXN],ans[MAXN];
vector<array<int,3>>query[MAXN];
vector<int>upd[MAXN];
int r[MAXN];
int main()
{
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		upd[i] = {0};
		char c;
		cin>>c;
		a[i] = c-'0';
	}
	int cnt = 0;
	for(int i=1;i<=q;i++){
		string s;
		cin>>s;
		if(s=="toggle"){
			int x;cin>>x;
			upd[x].push_back(i);
		}else{
			int a,b;
			cin>>a>>b;
			query[b-1].push_back({a,i,cnt++});
		}
	}
	for(int i=1;i<=n;i++){
		int c = a[i];
		upd[i].push_back(q+1);
		for(int j=0;j+1<(int)(upd[i].size());j++){
			for(int k = upd[i][j];k<upd[i][j+1];k++){
				if(c)r[k]++;
				else r[k] = 0;
			}
			c^=1;
		}
		for(auto x:query[i]){
			int res = 0;
			for(int j=0;j<x[1];j++){
				res+=r[j] >= i - x[0]+1;
			}
			ans[x[2]] = res;
		}
		//for(int j=0;j<=q;j++)cout<<r[j]<<" ";
		//cout<<'\n';
	}
	for(int i=0;i<cnt;i++)cout<<ans[i]<<'\n';
	
	
}

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