oj.uz

Submission #932028

# Submission time Handle Problem Language Result Execution time Memory
932028 2024-02-22T20:18:44 Z amirhoseinfar1385 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 887 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10;
int n,q,all[maxn],res[maxn],now,qu[maxn];
set<int>st;
int fn[maxn],kaf=(1<<19);

struct offt2fen{
	vector<pair<int,int>>ady[maxn];
	void upd(int l,int r,int w){
		//cout<<"updy: "<<l<<" "<<r<<" "<<w<<endl;
		l++;
		r++;
		while(l<maxn){
			int fr=r;
			while(fr<maxn){
				ady[l].push_back(make_pair(-fr,w));
				fr+=(fr&(-fr));
			}
			l+=((-l)&l);
		}
	}
	void pors(int l,int r,int w){
		//cout<<"porsi: "<<l<<" "<<r<<" "<<w<<endl;
		l++;
		r++;
		while(l>0){
			int fr=r;
			while(fr>0){
				ady[l].push_back(make_pair(fr,w));
				fr-=(fr&(-fr));
			}
			l-=((-l)&l);
		}
	}
	void cal(int i){
		for(auto x:ady[i]){
			if(x.first<0){
				x.first=-x.first;
				fn[x.first]+=x.second;
			}
			else{
				res[x.second]+=fn[x.first];
			}
		}
		for(auto x:ady[i]){
			fn[x.first]=0;
		}
	}
	void build(){
		for(int i=0;i<maxn;i++){
			cal(i);
		}
	}
}fen;

struct segment{
	long long seg[(1<<20)];
	void upd(int i,int w){
		//cout<<"hey: "<<i-kaf<<" "<<w<<endl;
		while(i>0){
			if(i>=kaf){
				seg[i]=w;
			}
			else{
				seg[i]=max(seg[(i<<1)],seg[(i<<1)^1]);
			}
			i>>=1;
		}
	}
	int pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		int m=(l+r)>>1;
		return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
	}
}seg;

int calu(int l,int r,int w=1,int z=-1){
	if(l>r){
		return -1;
	}
	int t=now-seg.pors(1,0,kaf-1,l,r);
	if(z!=-1){
		t=z;
	}
	fen.upd(l,l,t*w);
	fen.upd(l,r+1,-t*w);
	fen.upd(r+1,l,-t*w);
	fen.upd(r+1,r+1,t*w);
	return t;
}

void upd(int ind){
	st.erase(ind);
	auto y=st.lower_bound(ind);
	int nx=*y;
	y--;
	int ps=*y;
	if(all[ind]){
		//calu(ind+1,nx-1);
		//calu(ps+1,ind-1);
		seg.upd(ind+kaf,now);
	}
	else{
		int x=calu(ps+1,nx-1);
		calu(ps+1,ind-1,-1,x);
		calu(ind+1,nx-1,-1,x);
		seg.upd(ind+kaf,maxn+10);
		st.insert(ind);
	}
	all[ind]^=1;
}

void pors(int l,int r){
	//cout<<"Wtf: "<<l<<" "<<r<<" "<<seg.pors(1,0,kaf-1,l,r)<<endl;
	res[now]+=max(0,now-seg.pors(1,0,kaf-1,l,r));
	fen.pors(l,r,now);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	cin>>n>>q;
	st.insert(0);
	st.insert(n+1);
	for(int i=1;i<=n;i++){
		char c;
		cin>>c;
		all[i]=c-'0';
		all[i]^=1;
		if(all[i]==1){
			st.insert(i);
			seg.upd(i+kaf,maxn+10);
		}
	}
	for(int i=1;i<=q;i++){
		now=i;
		string s;
		int l,r;
		cin>>s>>l;
		if(s[0]=='q'){
			cin>>r;
			r--;
			pors(l,r);
			qu[now]=1;
		}
		else{
			upd(l);
		}
	}
	fen.build();
	for(int i=1;i<=q;i++){
		if(qu[i]==1){
			cout<<res[i]<<"\n";
		}
	}
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 724 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 355 ms 35724 KB Output is correct
6 Correct 529 ms 98340 KB Output is correct
7 Correct 666 ms 169728 KB Output is correct
8 Correct 783 ms 264528 KB Output is correct
9 Correct 120 ms 45228 KB Output is correct
10 Correct 125 ms 46736 KB Output is correct
11 Correct 135 ms 53532 KB Output is correct
12 Correct 887 ms 282956 KB Output is correct
13 Correct 782 ms 263100 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 17240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -