Submission #497050

#	Time	Username	Problem	Language	Result	Execution time	Memory
497050		jamezzz	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1378 ms	256460 KiB

street_lamps

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

//build a segtree on time
//left-update-right dnc on right

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define maxn 300005

struct upd{
	int l,st,et,v;
	bool operator< (const upd &u){
		return this->l<u.l;
	}
};

struct qry{
	int l,t;
	bool operator< (const qry &q){
		return this->l<q.l;
	}
};

int n,q,state[maxn],ans[maxn],f1[maxn+5],f2[maxn+5];
char c,s[6];

void up(int x,int v,int* f){
	while(x<=q+5)f[x]+=v,x+=x&-x;
}

void up(int l,int r,int v){
	++l;++r;
	up(l,v,f1);up(r+1,-v,f1);
	up(l,-v*(l-1),f2);up(r+1,v*r,f2);
}

int sum(int x,int* f){
	int res=0;
	while(x)res+=f[x],x-=x&-x;
	return res;
}

int sum(int x){
	return x*sum(x,f1)+sum(x,f2);
}

int sum(int l,int r){
	++l;++r;
	return sum(r)-sum(l-1);
}

int stime[maxn];
set<ii> ranges;
vector<upd> updates[maxn],tmpu;
vector<qry> queries[maxn],tmpq;

void add_upd(int l,int r,int st,int et){
	updates[l].push_back({l,st,et,1});
	updates[r+1].push_back({l,st,et,-1});
}

void dnc(int l,int r){
	if(l==r){
		int ptr=0;
		for(qry &i:queries[l]){
			while(ptr<sz(updates[l])&&updates[l][ptr].l<=i.l){
				upd &u=updates[l][ptr];
				up(u.st,u.et,u.v);
				++ptr;
			}
			ans[i.t+1]+=sum(0,i.t);
		}
		for(int i=0;i<ptr;++i){
			upd &u=updates[l][i];
			up(u.st,u.et,-u.v);
		}
		return;
	}
	int m=(l+r)/2;
	dnc(l,m);dnc(m+1,r);
	
	vector<upd> &lupd=updates[l],&rupd=updates[m+1];
	vector<qry> &lqry=queries[l],&rqry=queries[m+1];
	
	int ptr=0;
	for(qry &i:rqry){
		while(ptr<sz(lupd)&&lupd[ptr].l<=i.l){
			up(lupd[ptr].st,lupd[ptr].et,lupd[ptr].v);
			++ptr;
		}
		ans[i.t+1]+=sum(0,i.t);
	}
	for(int i=0;i<ptr;++i){
		up(lupd[i].st,lupd[i].et,-lupd[i].v);
	}
	
	merge(all(lupd),all(rupd),back_inserter(tmpu));
	merge(all(lqry),all(rqry),back_inserter(tmpq));
	swap(tmpu,updates[l]);
	swap(tmpq,queries[l]);
	tmpq.clear();
	tmpu.clear();
}

int main(){
	sf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		sf(" %c",&c);
		state[i]=c-'0';
	}
	int pv=-1;
	for(int i=1;i<=n;++i){
		if(state[i]==1&&state[i-1]==0)pv=i;
		if(state[i]==1&&state[i+1]==0){
			ranges.insert({pv,i});
			stime[pv]=0;
		}
	}
	
	memset(ans,-1,sizeof ans);
	for(int i=1;i<=q;++i){
		sf(" %s",&s);
		if(s[0]=='t'){
			int x;sf("%d",&x);
			if(state[x]==1){
				state[x]=0;
				auto it=--ranges.upper_bound({x,INF});
				int l=it->fi,r=it->se;
				ranges.erase(it);
				add_upd(l,r,stime[l],i-1);
				if(l<x)stime[l]=i,ranges.insert({l,x-1});
				if(x<r)stime[x+1]=i,ranges.insert({x+1,r});
			}
			else{
				state[x]=1;
				int nl=x,nr=x;
				auto it=ranges.upper_bound({x,INF});
				if(it!=ranges.begin()){
					--it;
					int l=it->fi,r=it->se;
					if(r==x-1){
						ranges.erase(it);
						add_upd(l,r,stime[l],i-1);
						nl=l;
					}
				}
				it=ranges.upper_bound({x,INF});
				if(it!=ranges.end()){
					int l=it->fi,r=it->se;
					if(x+1==l){
						ranges.erase(it);
						add_upd(l,r,stime[l],i-1);
						nr=r;
					}
				}
				stime[nl]=i;
				ranges.insert({nl,nr});
			}
		}
		else{
			int l,r;sf("%d%d",&l,&r);
			queries[r-1].pb({l,i-1});
			ans[i]=0;
		}
	}
	auto it=ranges.begin();
	while(it!=ranges.end()){
		add_upd(it->fi,it->se,stime[it->fi],q);
		++it;
	}
	
	for(int i=1;i<=n+1;++i){
		sort(all(queries[i]));
		sort(all(updates[i]));
	}
	dnc(1,n+1);
	
	for(int i=1;i<=q;++i){
		if(ans[i]!=-1)pf("%d\n",ans[i]);
	}
}

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

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:148:9: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[6]' [-Wformat=]
  148 |   sf(" %s",&s);
      |        ~^  ~~
      |         |  |
      |         |  char (*)[6]
      |         char*
street_lamps.cpp:132:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |  sf("%d%d",&n,&q);
      |    ^
street_lamps.cpp:134:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |   sf(" %c",&c);
      |     ^
street_lamps.cpp:148:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |   sf(" %s",&s);
      |     ^
street_lamps.cpp:150:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |    int x;sf("%d",&x);
      |            ^
street_lamps.cpp:187:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |    int l,r;sf("%d%d",&l,&r);
      |              ^

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