제출 #336666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336666		errorgorn	가로등 (APIO19_street_lamps)	C++17	100 / 100	2754 ms	95344 KiB

street_lamps

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct U{
	int typ;
	int a,b;
	int t;
	int id;
};

int n,q;
string st;
set<ii> s;
vector<U> upd;
int ans[300005];

void add(ii range, int t){
	s.insert(range);
	upd.push_back({1,range.fi,range.se,t,1});
}

void rem(ii range,int t){
	s.erase(range);
	upd.push_back({1,range.fi,range.se,t,-1});
}

int fen[300005];

void inc(int i,int j){
	while (i<=300005){
		fen[i]+=j;
		i+=i&-i;
	}
}

int query(int i){
	int res=0;
	while (i){
		res+=fen[i];
		i-=i&-i;
	}
	return res;
}

void dnc(int l,int r,vector<U> upd){
	int m=l+r>>1;
	vector<U> lupd,rupd;
	set<int> s;
	
	//cout<<"rec: "<<l<<" "<<r<<" "<<sz(upd)<<endl;
	
	for (auto &it:upd){
		if (it.typ==1){ //upd
			if (it.id==1){ //adding
				inc(it.a,-it.t);
				s.insert(it.a);
			}
			else{ //erasing
				inc(it.a,it.t);
				s.erase(it.a);
			}
			
			if (it.b<=m) lupd.push_back(it);
			else rupd.push_back(it);
		}
		else{
			//cout<<"debug: "<<it.b<<endl;
			if (it.b<=l){ //[l,r] completely in [it.b,N]
				//cout<<l<<" "<<r<<" "<<it.id<<endl;
				ans[it.id]+=query(it.a);
				if (!s.empty() && *s.begin()<=it.a) ans[it.id]+=it.t;
			}
			else{
				if (it.b<=m) lupd.push_back(it);
				rupd.push_back(it);
			}
		}
	}
	
	//reset fenwick
	for (auto &it:upd){
		if (it.typ==1) inc(it.a,it.t*it.id);
	}
	
	if (l==r) return;
	dnc(l,m,lupd);
	dnc(m+1,r,rupd);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>q;
	cin>>st;
	st="$"+st;
	
	ii curr=ii(-1,-1);
	rep(x,1,sz(st)){
		if (st[x]=='1'){
			if (curr.fi==-1) curr.fi=x;
			curr.se=x;
		}
		else{
			if (curr.fi!=-1){
				add(curr,0);
				curr=ii(-1,-1);
			}
		}
	}
	
	if (curr!=ii(-1,-1)){
		add(curr,0);
	}
	
	string typ;
	int a,b;
	int IDX=0;
	
	rep(x,1,q+1){
		cin>>typ;
		
		if (typ=="query"){
			cin>>a>>b;
			
			upd.push_back({2,a,b-1,x,IDX++});
		}
		else{
			cin>>a;
			
			if (st[a]=='0'){
				ii range=ii(a,a);
				auto it=s.lower_bound(ii(a,-1));
				if (it!=s.end() && (*it).fi==a+1) range.se=(*it).se;
				if (it!=s.begin() && (*prev(it)).se==a-1) range.fi=(*prev(it)).fi;
				
				if (range.fi!=a) rem(ii(range.fi,a-1),x);
				if (range.se!=a) rem(ii(a+1,range.se),x);
				add(range,x);
				
				st[a]='1';
			}
			else{
				ii range=*--s.lower_bound(ii(a,1e9));
				
				rem(range,x);
				if (range.fi!=a) add(ii(range.fi,a-1),x);
				if (range.se!=a) add(ii(a+1,range.se),x);
				
				st[a]='0';
			}
			
			//for (auto &it:s) cout<<it.fi<<"_"<<it.se<<" "; cout<<endl;
		}
	}
	
	dnc(1,n,upd);
	rep(x,0,IDX) cout<<ans[x]<<endl;
}

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In function 'void add(std::pair<long long int, long long int>, int)':
street_lamps.cpp:14:12: warning: narrowing conversion of 'range.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
   14 | #define fi first
      |            ^
street_lamps.cpp:43:25: note: in expansion of macro 'fi'
   43 |  upd.push_back({1,range.fi,range.se,t,1});
      |                         ^~
street_lamps.cpp:15:12: warning: narrowing conversion of 'range.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
   15 | #define se second
      |            ^
street_lamps.cpp:43:34: note: in expansion of macro 'se'
   43 |  upd.push_back({1,range.fi,range.se,t,1});
      |                                  ^~
street_lamps.cpp: In function 'void rem(std::pair<long long int, long long int>, int)':
street_lamps.cpp:14:12: warning: narrowing conversion of 'range.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
   14 | #define fi first
      |            ^
street_lamps.cpp:48:25: note: in expansion of macro 'fi'
   48 |  upd.push_back({1,range.fi,range.se,t,-1});
      |                         ^~
street_lamps.cpp:15:12: warning: narrowing conversion of 'range.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
   15 | #define se second
      |            ^
street_lamps.cpp:48:34: note: in expansion of macro 'se'
   48 |  upd.push_back({1,range.fi,range.se,t,-1});
      |                                  ^~
street_lamps.cpp: In function 'void dnc(int, int, std::vector<U>)':
street_lamps.cpp:70:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int m=l+r>>1;
      |        ~^~

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