oj.uz

Submission #932023

# Submission time Handle Problem Language Result Execution time Memory
932023 2024-02-22T20:07:41 Z amirhoseinfar1385 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 946 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;

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,-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 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 669 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 16728 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 3 ms 13056 KB Output is correct
5 Correct 339 ms 35676 KB Output is correct
6 Correct 535 ms 98072 KB Output is correct
7 Correct 683 ms 170028 KB Output is correct
8 Correct 815 ms 259340 KB Output is correct
9 Correct 112 ms 43068 KB Output is correct
10 Correct 122 ms 43820 KB Output is correct
11 Correct 131 ms 50836 KB Output is correct
12 Correct 946 ms 277480 KB Output is correct
13 Correct 818 ms 258292 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 17244 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 -