Submission #367809

#	Time	Username	Problem	Language	Result	Execution time	Memory
367809		YJU	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2997 ms	49716 KiB

street_lamps

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=3e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
 
char c;
ll n,q,x,y,state[N],ans[N],ty[N];
string s;
vector<pair<pll,pll> > ioi;
set<ll> location;
 
ll find_R(ll idx){
	return *location.lwb(idx)-1;
}
 
ll find_L(ll idx){
	return *prev(location.lwb(idx+1))+1;
}
 
void upd(ll idx){
	state[idx]^=1;
	if(state[idx]==0){
		location.insert(idx);
	}else{
		location.erase(idx);
	}
}

ll bit[N];

void add(ll idx,ll d){
	if(!d)return ;
	for(int i=idx;i<N;i+=(i&-i)){
		bit[i]+=d;
	}
}

ll query(ll idx){
	ll tmp=0;
	for(int i=idx;i>0;i-=(i&-i)){
		tmp+=bit[i];
	}
	return tmp;
}

void CDQ(ll l,ll r){
	if(l==r-1)return ;
	ll mid=(l+r)>>1;
	CDQ(l,mid);CDQ(mid,r);
	ll iter=l;
	for(int i=mid;i<r;i++){
		while(iter<mid&&ioi[iter].X.Y<=ioi[i].X.Y)add(ioi[iter].Y.X,ioi[iter].X.X*ioi[iter].Y.Y),iter++;
		if(ioi[i].Y.Y==0){
			ans[ioi[i].X.X]+=query(ioi[i].Y.X);
		}
	}
	while(iter>l)iter--,add(ioi[iter].Y.X,-ioi[iter].X.X*ioi[iter].Y.Y);
	
	sort(ioi.begin()+l,ioi.begin()+r,[](pair<pll,pll> A,pair<pll,pll> B){
		return (A.X.Y<B.X.Y);
	});
}
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q;
	REP(i,n+2)location.insert(i);
	REP1(i,n){
		cin>>c;
		if(c=='1')upd(i);
	}
	REP1(i,q){
		cin>>s;
		if(s[0]=='q'){
			ty[i]=2;
			cin>>x>>y;
			--y;
			///cout<<"query "<<i<<" "<<x<<" "<<y<<" "<<find_R(1,1,n+1,x)<<"\n";
			if(find_R(x)>=y){ans[i]+=i;}
			ioi.pb(mp(mp(i,x),mp(y,0)));
		}else{
			ty[i]=1;
			cin>>x;
			ll L=find_L(x-1),R=find_R(x+1);
			//cout<<x<<" "<<L<<" "<<R<<"\n";
			if(state[x]==0){
				//[L,x] [x,R]-=i;
				ioi.pb(mp(mp(i,L),mp(x,-1)));
				ioi.pb(mp(mp(i,L),mp(R+1,1)));
				ioi.pb(mp(mp(i,x+1),mp(x,1)));
				ioi.pb(mp(mp(i,x+1),mp(R+1,-1)));
			}else{
				//[L,x] [x,R] +=i ;
				ioi.pb(mp(mp(i,L),mp(x,1)));
				ioi.pb(mp(mp(i,L),mp(R+1,-1)));
				ioi.pb(mp(mp(i,x+1),mp(x,-1)));
				ioi.pb(mp(mp(i,x+1),mp(R+1,1)));
			}
			upd(x);
		}
	}
	sort(ioi.begin(),ioi.end());
	CDQ(0,SZ(ioi));
	/*
	REP(i,SZ(ioi)){
		if(ioi[i].Y.Y==0){
			REP(j,i){
				if(ioi[j].Y.Y!=0&&ioi[j].X.Y<=ioi[i].X.Y&&ioi[j].Y.X<=ioi[i].Y.X){
					ans[ioi[i].X.X]+=(ioi[j].X.X*ioi[j].Y.Y);
				}
			}
		}
	}
	*/
	REP1(i,q){
		if(ty[i]==2)cout<<ans[i]<<"\n";
	}
	return 0;
}

Compilation message (stderr)

street_lamps.cpp:11:18: warning: overflow in conversion from 'long long int' to 'll' {aka 'int'} changes value from '1152921504606846976' to '0' [-Woverflow]
   11 | const ll INF=(1LL<<60);
      |              ~~~~^~~~~

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