Submission #307710

#	Time	Username	Problem	Language	Result	Execution time	Memory
307710		noclever	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1522 ms	46220 KiB

street_lamps

#include<bits/stdc++.h>
#define ll long long
#define N 300005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n,m;
char s[N];
struct interval {
	int lp,rp;
	int l,r;
	interval() {}
	interval(int _lp,int _rp,int _l,int _r) {lp=_lp,rp=_rp,l=_l,r=_r;}
	bool operator <(const interval &a)const {return rp<a.rp;}
}t[N<<2];

set<int>pos;
set<int>::iterator it;
int id[N],R[N];
int tot;
int ans[N];

struct query {
	int l,r,tim,id;
}q[N];

int qt;
struct node {
	int op,id,r;
	node() {}
	node(int _op,int _id,int _r) {
		op=_op,id=_id,r=_r;
	}
};

bool cmpr(const node &a,const node &b) {
	if(a.r!=b.r) return a.r>b.r;
	return a.op<b.op;
}

bool cmpl(const node &a,const node &b) {
	if(a.op!=b.op) return a.op<b.op;
	if(a.op==1) return t[a.id].lp<t[b.id].lp;
	else return q[a.id].l<q[b.id].l;
}

node st[N<<2];
int top;

struct tree {
	int l,r;
	int sum,tag;
}tr[N<<2];

void update(int v) {tr[v].sum=tr[v<<1].sum+tr[v<<1|1].sum;}
void Add(int v,int f) {tr[v].sum+=(tr[v].r-tr[v].l+1)*f,tr[v].tag+=f;}
void down(int v) {
	if(tr[v].tag) {
		Add(v<<1,tr[v].tag);
		Add(v<<1|1,tr[v].tag);
		tr[v].tag=0;
	}
}
void build(int v,int l,int r) {
	tr[v].l=l,tr[v].r=r;
	if(l==r) return ;
	int mid=l+r>>1;
	build(v<<1,l,mid),build(v<<1|1,mid+1,r);
}

void Modify(int v,int l,int r,int f) {
	if(tr[v].l>r||tr[v].r<l) return ;
	if(l<=tr[v].l&&tr[v].r<=r) {
		Add(v,f);
		return ;
	}
	down(v);
	Modify(v<<1,l,r,f),Modify(v<<1|1,l,r,f);
	update(v);
}

int query(int v,int l,int r) {
	if(tr[v].l>r||tr[v].r<l) return 0;
	if(l<=tr[v].l&&tr[v].r<=r) return tr[v].sum;
	down(v);
	return query(v<<1,l,r)+query(v<<1|1,l,r);
}

void solve(int l,int r) {
	if(l==r) return ;
	int mid=l+r>>1;
	solve(l,mid),solve(mid+1,r);
	int tag=l;
	for(int i=mid+1;i<=r;i++) {
		if(st[i].op==1) continue ;
		while(tag<=mid&&st[tag].op==1&&t[st[tag].id].lp<=q[st[i].id].l) {
			Modify(1,t[st[tag].id].l,t[st[tag].id].r,1);
			tag++;
		}
		ans[st[i].id]+=query(1,1,q[st[i].id].tim);
	}
	for(int i=l;i<tag;i++) Modify(1,t[st[i].id].l,t[st[i].id].r,-1);
	inplace_merge(st+l,st+mid+1,st+r+1,cmpl);
}

int main() {
	n=Get(),m=Get();
	scanf("%s",s+1);
	char op[20];
	build(1,1,m);
	for(int i=1;i<=n;i++) {
		if(s[i]=='0') continue ;
		int j;
		for(j=i;j<=n&&s[j]=='1';j++);
		j--;
		R[i]=j;
		pos.insert(i);
		t[id[i]=++tot]=interval(i,j,1,m);
		i=j;
	}
	
	for(int i=1;i<=m;i++) {
		scanf("%s",op+1);
		int x;
		if(op[1]=='t') {
			x=Get();
			if(i==m) continue ;
			s[x]^=1;
			if(s[x]=='0') {
				it=pos.upper_bound(x);it--;
				int LL=*it,RR=R[LL];
				t[id[LL]].r=i;
				if(LL<x) {
					t[id[LL]=++tot]=interval(LL,x-1,i+1,m);
					R[LL]=x-1;
				} else pos.erase(LL);
				if(x<RR) {
					t[id[x+1]=++tot]=interval(x+1,RR,i+1,m);
					R[x+1]=RR;
					pos.insert(x+1);
				}
			} else {
				int nowl=x,nowr=x;
				it=pos.upper_bound(x);
				if(it!=pos.end()) {
					int y=*it;
					if(y==x+1) {
						nowr=R[y];
						t[id[y]].r=i;
						pos.erase(y);
					}
				}
				it=pos.lower_bound(x);
				if(it!=pos.begin()) {
					int y=*(--it);
					if(R[y]==x-1) {
						nowl=y;
						t[id[y]].r=i;
						pos.erase(y);
					}
				}
				t[id[nowl]=++tot]=interval(nowl,nowr,i+1,m);
				R[nowl]=nowr;
				pos.insert(nowl);
			}
		} else {
			q[++qt].l=Get(),q[qt].r=Get()-1;
			q[qt].id=qt,q[qt].tim=i;
		}
	}
	for(int i=1;i<=tot;i++) {
		st[++top]=node(1,i,t[i].rp);
	}
	for(int i=1;i<=qt;i++) {
		st[++top]=node(2,i,q[i].r);
	}
	sort(st+1,st+1+top,cmpr);
	solve(1,top);
	for(int i=1;i<=qt;i++) cout<<ans[i]<<"\n";
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:68:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |  int mid=l+r>>1;
      |          ~^~
street_lamps.cpp: In function 'void solve(int, int)':
street_lamps.cpp:92:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |  int mid=l+r>>1;
      |          ~^~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |  scanf("%s",s+1);
      |  ~~~~~^~~~~~~~~~
street_lamps.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |   scanf("%s",op+1);
      |   ~~~~~^~~~~~~~~~~

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