Submission #756115

#	Time	Username	Problem	Language	Result	Execution time	Memory
756115		boyliguanhan	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	4062 ms	179024 KiB

street_lamps

#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
#define gc getchar
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
int n,N,T,root[600001],cnt;
struct node{
	int l,r,sum;
}seg[15020001];
#define mid ((lb+rb)>>1)
void Update(int &rt,int lb,int rb,int pos,int w){
	if (!rt) rt=++cnt;seg[rt].sum+=w;
	if (lb==rb) return;
	(mid>=pos?Update(seg[rt].l,lb,mid,pos,w):Update(seg[rt].r,mid+1,rb,pos,w));
}
int Query(int rt,int lb,int rb,int l,int r){
	if (!rt||lb>r||rb<l) return 0;
	if (lb>=l&&rb<=r) return seg[rt].sum;
	return Query(seg[rt].l,lb,mid,l,r)+Query(seg[rt].r,mid+1,rb,l,r);
}
inline void update(int pos,int r,int w){
	for (;pos<=n+1;pos+=pos&-pos) Update(root[pos],1,n+1,r,w);
}
inline int query(int posx,int posy){
	int ans=0;
	for (;posx;posx-=posx&-posx) ans+=Query(root[posx],1,n+1,1,posy);
	return ans;
}
inline void Add(int x1,int y1,int x2,int y2,int W){
	update(x1,y1,W);update(x1,y2+1,-W);
	update(x2+1,y1,-W);update(x2+1,y2+1,W);
}
struct road{
	int l,r;
};
inline bool operator < (road a,road b){
	return a.r<b.r;
} 
set<road> S;
set<road>::iterator it;
bool zt[2000001];
signed main(){
	n=1+read(),T=read();N=n-1;
	for (int i=1;i<=n;i++){
		S.insert((road){i,i});
	}
	for (int i=1;i<=N;i++){
		char ch=gc();
		while (!isdigit(ch)) ch=gc();
		zt[i]=(ch-48);
		if (zt[i]){
			it=S.lower_bound((road){0,i+1});it--;
			int lb=(*it).l;
			S.erase(it);S.erase((road){i+1,i+1});
			S.insert((road){lb,i+1});
		}
	}
	for (it=S.begin();it!=S.end();++it){
		Add((*it).l,(*it).l,(*it).r,(*it).r,T);
	}
	for (int t=1;t<=T;t++){
		char s[11];scanf("%s",s+1);
		if (s[1]=='q'){
			int x=read(),y=read();
			int ans=query(x,y);
			int X=(*(S.lower_bound((road){0,x}))).l;
			int Y=(*(S.lower_bound((road){0,y}))).l;
			printf("%d\n",ans-(T-t)*(X==Y));
		}else if (s[1]=='t'){
			int x=read();
			if (zt[x]==1){
				it=S.lower_bound((road){0,x});
				int lb1=(*it).l,rb1=x;
				int lb2=x+1,rb2=(*it).r;
				Add(lb1,lb2,rb1,rb2,t-T);
				S.erase((road){lb1,rb2});
				S.insert((road){lb1,rb1});S.insert((road){lb2,rb2}); 
				zt[x]^=1;
			}else{
				it=S.lower_bound((road){0,x});
				int lb1=(*it).l,rb1=x;
				it++;
				int lb2=x+1,rb2=(*it).r;
				Add(lb1,lb2,rb1,rb2,T-t);
				S.erase((road){lb1,rb1});S.erase((road){lb2,rb2});
				S.insert((road){lb1,rb2}); 
				zt[x]^=1;
			}
		}
	}
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'long long int read()':
street_lamps.cpp:7:17: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    7 |     register ll x=0,f=1;char ch=gc();
      |                 ^
street_lamps.cpp:7:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    7 |     register ll x=0,f=1;char ch=gc();
      |                     ^
street_lamps.cpp: In function 'void Update(int&, int, int, int, int)':
street_lamps.cpp:18:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   18 |  if (!rt) rt=++cnt;seg[rt].sum+=w;
      |  ^~
street_lamps.cpp:18:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   18 |  if (!rt) rt=++cnt;seg[rt].sum+=w;
      |                    ^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:68:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   char s[11];scanf("%s",s+1);
      |              ~~~~~^~~~~~~~~~

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