제출 #407001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407001		amunduzbaev	가로등 (APIO19_street_lamps)	C++14	20 / 100	128 ms	22672 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[4*M], p[4*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);
}

void sett2(int i, int v, int lx = 0, int rx = M, int x = 1){
	if(lx == rx) { tree[x] = v; return; }
	int m = (lx + rx)>>1;
	if(i <= m) sett(i, v, lx, m, x<<1);
	else sett(i, v, m+1, rx, x<<1|1);
	tree[x] = max(tree[x<<1], tree[x<<1|1]);
}

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

/*

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

5 7
11011
query 1 2
query 1 2
query 5 6
query 3 4
toggle 3
query 3 4
query 5 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});
	} 

	//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+1);
		//} 
		//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+1]<<"\n";
		//} cout<<"\n"; 
		
		//return 0;
	//} 
	
	//else {
		for(int i=0;i<n;i++) if(a[i]) sett2(i, 0);
		for(int i=0;i<sz(tt);i++){
			if(tt[i].ff == -1) sett2(tt[i].ss, i+1);
		} for(int i=0;i<m;i++){
			if(~tt[i].ff) cout<<max((i - rmq(tt[i].ff, tt[i].ss) + 1), 0ll)<<"\n";
		}
	//}
	return 0;
}

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