oj.uz

Submission #932021

# Submission time Handle Problem Language Result Execution time Memory
932021 2024-02-22T20:04:40 Z amirhoseinfar1385 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 896 ms 524292 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;

void calu(int l,int r,int w=1){
	if(l>r){
		return ;
	}
	int t=now-seg.pors(1,0,kaf-1,l,r);
	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);
}

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{
		calu(ps+1,nx-1);
		calu(ps+1,ind-1,-1);
		calu(ind+1,nx,-1);
		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 17244 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 663 ms 524292 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 4 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 339 ms 35660 KB Output is correct
6 Correct 549 ms 98052 KB Output is correct
7 Correct 660 ms 168728 KB Output is correct
8 Correct 818 ms 262896 KB Output is correct
9 Correct 118 ms 45600 KB Output is correct
10 Correct 126 ms 47244 KB Output is correct
11 Correct 137 ms 52000 KB Output is correct
12 Correct 896 ms 281912 KB Output is correct
13 Correct 779 ms 262460 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 17244 KB Output isn't correct
2 Halted 0 ms 0 KB -