oj.uz

Submission #932064

# Submission time Handle Problem Language Result Execution time Memory
932064 2024-02-22T21:33:51 Z amirhoseinfar1385 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2822 ms 485520 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+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){
			if(l<0){
				return ;
			}
			ady[l].push_back(make_pair(-r,w));
			l+=((-l)&l);
		}
	}
	void pors(int l,int r,int w){
		////cout<<"porsi: "<<l<<" "<<r<<" "<<w<<endl;
		l++;
		r++;
		while(l>0){
			ady[l].push_back(make_pair(r,w));
			l-=((-l)&l);
		}
	}
	void cal(int i){
		for(auto x:ady[i]){
			if(x.first<0){
				x.first=-x.first;
				while(x.first<maxn){
					fn[x.first]+=x.second;
					x.first+=((-x.first)&x.first);
				}
			}
			else{
				while(x.first>0){
					res[x.second]+=fn[x.first];
					x.first-=((-x.first)&x.first);
				}
			}
		}
		for(auto x:ady[i]){
			if(x.first<0){
				x.first=-x.first;
				while(x.first<maxn){
					fn[x.first]=0;
					x.first+=((-x.first)&x.first);
				}
			}
		}
	}
	void build(){
		for(int i=0;i<maxn;i++){
			cal(i);
		}
	}
}fen;

void calu(int l,int r,int w){
	if(l>r){
		return ;
	}
	fen.upd(l,l,w);
	fen.upd(l,r+1,-w);
	fen.upd(r+1,l,-w);
	fen.upd(r+1,r+1,w);
}

void upd(int ind){
	st.erase(ind);
	if(ind>=(*st.rbegin())||(ind<=(*st.begin()))){
		return ;
	}
	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);
		calu(ps+1,ind-1,-(maxn-now));
		calu(ind+1,nx-1,-(maxn-now));
		calu(ps+1,nx-1,maxn-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);
		calu(ps+1,nx-1,-(maxn-now));
		calu(ps+1,ind-1,(maxn-now));
		calu(ind+1,nx-1,(maxn-now));
		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));
	auto x=*st.lower_bound(l);
	//cout<<"wtf: "<<l<<" "<<x<<" "<<r<<endl;
	if(x>r){
		res[now]-=maxn-now;
	}
	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);
	calu(1,n,maxn);
	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);
			all[i]=0;
			upd(i);
		}
	}
	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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 6 ms 16988 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Correct 5 ms 16988 KB Output is correct
6 Correct 4 ms 17000 KB Output is correct
7 Correct 4 ms 19288 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1173 ms 191412 KB Output is correct
2 Correct 1095 ms 202172 KB Output is correct
3 Correct 907 ms 195300 KB Output is correct
4 Correct 1792 ms 302992 KB Output is correct
5 Correct 1630 ms 281704 KB Output is correct
6 Correct 1894 ms 357592 KB Output is correct
7 Correct 1846 ms 315528 KB Output is correct
8 Correct 245 ms 59056 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19028 KB Output is correct
2 Correct 14 ms 18780 KB Output is correct
3 Correct 11 ms 18520 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 2822 ms 485520 KB Output is correct
6 Correct 2345 ms 421188 KB Output is correct
7 Correct 1619 ms 274300 KB Output is correct
8 Correct 262 ms 49780 KB Output is correct
9 Correct 60 ms 26124 KB Output is correct
10 Correct 65 ms 26872 KB Output is correct
11 Correct 66 ms 26936 KB Output is correct
12 Correct 1824 ms 295668 KB Output is correct
13 Correct 244 ms 49888 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17752 KB Output is correct
2 Correct 9 ms 18012 KB Output is correct
3 Correct 13 ms 18584 KB Output is correct
4 Correct 13 ms 18776 KB Output is correct
5 Correct 1210 ms 208224 KB Output is correct
6 Correct 1523 ms 270896 KB Output is correct
7 Correct 1893 ms 346692 KB Output is correct
8 Correct 2295 ms 425996 KB Output is correct
9 Correct 1481 ms 267460 KB Output is correct
10 Correct 2187 ms 334964 KB Output is correct
11 Correct 1484 ms 280408 KB Output is correct
12 Correct 2164 ms 342732 KB Output is correct
13 Correct 1458 ms 273148 KB Output is correct
14 Correct 2169 ms 348708 KB Output is correct
15 Correct 1791 ms 304432 KB Output is correct
16 Correct 236 ms 55728 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 6 ms 16988 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Correct 5 ms 16988 KB Output is correct
6 Correct 4 ms 17000 KB Output is correct
7 Correct 4 ms 19288 KB Output is correct
8 Correct 1173 ms 191412 KB Output is correct
9 Correct 1095 ms 202172 KB Output is correct
10 Correct 907 ms 195300 KB Output is correct
11 Correct 1792 ms 302992 KB Output is correct
12 Correct 1630 ms 281704 KB Output is correct
13 Correct 1894 ms 357592 KB Output is correct
14 Correct 1846 ms 315528 KB Output is correct
15 Correct 245 ms 59056 KB Output is correct
16 Correct 17 ms 19028 KB Output is correct
17 Correct 14 ms 18780 KB Output is correct
18 Correct 11 ms 18520 KB Output is correct
19 Correct 4 ms 19036 KB Output is correct
20 Correct 2822 ms 485520 KB Output is correct
21 Correct 2345 ms 421188 KB Output is correct
22 Correct 1619 ms 274300 KB Output is correct
23 Correct 262 ms 49780 KB Output is correct
24 Correct 60 ms 26124 KB Output is correct
25 Correct 65 ms 26872 KB Output is correct
26 Correct 66 ms 26936 KB Output is correct
27 Correct 1824 ms 295668 KB Output is correct
28 Correct 244 ms 49888 KB Output is correct
29 Correct 7 ms 17752 KB Output is correct
30 Correct 9 ms 18012 KB Output is correct
31 Correct 13 ms 18584 KB Output is correct
32 Correct 13 ms 18776 KB Output is correct
33 Correct 1210 ms 208224 KB Output is correct
34 Correct 1523 ms 270896 KB Output is correct
35 Correct 1893 ms 346692 KB Output is correct
36 Correct 2295 ms 425996 KB Output is correct
37 Correct 1481 ms 267460 KB Output is correct
38 Correct 2187 ms 334964 KB Output is correct
39 Correct 1484 ms 280408 KB Output is correct
40 Correct 2164 ms 342732 KB Output is correct
41 Correct 1458 ms 273148 KB Output is correct
42 Correct 2169 ms 348708 KB Output is correct
43 Correct 1791 ms 304432 KB Output is correct
44 Correct 236 ms 55728 KB Output is correct
45 Correct 995 ms 151744 KB Output is correct
46 Correct 778 ms 139440 KB Output is correct
47 Correct 837 ms 175740 KB Output is correct
48 Correct 1778 ms 304332 KB Output is correct
49 Correct 73 ms 30964 KB Output is correct
50 Correct 74 ms 30980 KB Output is correct
51 Correct 75 ms 31672 KB Output is correct
52 Correct 81 ms 34616 KB Output is correct
53 Correct 84 ms 34852 KB Output is correct
54 Correct 81 ms 34524 KB Output is correct