oj.uz

Submission #518319

# Submission time Handle Problem Language Result Execution time Memory
518319 2022-01-23T11:14:33 Z CSQ31 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1314 ms 37088 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define sz(a) (int)(a.size())
struct fenwick{
	vector<ll>bit;
	int n;
	void reset(int i){
		for(;i<=n;i+=i&(-i))bit[i]=0;
	}
	void upd(int i,int x){
		for(;i<=n;i+=i&(-i))bit[i]+=x;
	}
	ll query(int i){
		ll res = 0;
		for(;i>0;i-=i&(-i))res+=bit[i];
		return res;
	}
	fenwick(){}
	fenwick(int _n){
		n = _n;
		bit.assign(n+1,0);
	}
	
}sum,num,f;
struct line{
	int tl,tr,ql,qr;
	line(){}
	line(int _tl,int _tr,int _ql,int _qr){
		tl = _tl;
		tr = _tr;
		ql = _ql;
		qr = _qr;
	}
	
};vector<line>lines;

struct qq{
	int l,r,t;
	qq(){};
	qq(int _l,int _r,int _t):l(_l),r(_r),t(_t){}
};vector<qq>que;

const int MAXN = 3e5+5;
line st[MAXN];
int n,q,cnt = 0,ans[MAXN];
set<int>pos; //position of line heads
vector<array<int,2>>a;

/*
 * 	for(int i=1;i<=q;i++){
		for(auto q:que[i]){
			for(auto y:lines){
				if(y.tl <= i && y.ql <= q.l && q.r <= y.qr){
					ans[q.i]+=min(y.tr+1,i) - y.tl;
				} 	
			}
		}
		
	}
* */
void solve(int s,int t){
	if(s == t)return;
	int mid = (s+t)/2;
	solve(s,mid);
	solve(mid+1,t);
	vector<array<int,2>>add,ask;
	for(int i=s;i<=mid;i++){
		int x = a[i][1];
		if(x >= 0){
			add.push_back({lines[x].tl,x});
			add.push_back({lines[x].tr+1,x});
		}
	}
	for(int i=mid+1;i<=t;i++){
		int x = a[i][1];
		if(x < 0){
			x++;
			x*=-1;
			ask.push_back({que[x].t,x});
		}
	}
	sort(add.begin(),add.end());
	sort(ask.begin(),ask.end());
	/*
	if(t==3){
		cout<<"ranges"<<'\n';
		cout<<s<<" "<<mid<<" "<<t<<'\n';
		cout<<"add"<<'\n';
		for(auto x:add)cout<<x[0]<<" "<<x[1]<<'\n';
		cout<<"ask"<<'\n';
		for(auto x:ask)cout<<x[0]<<" "<<x[1]<<'\n';
	}*/
	int ptr = -1;
	for(auto x:ask){
		while(ptr+1 < sz(add) && add[ptr+1][0] <= x[0]){
			ptr++;
			int id = add[ptr][1];
			if(lines[id].tl == add[ptr][0]){ //add a line into the tl<=t<=tr case
				sum.upd(lines[id].qr,lines[id].tl);
				num.upd(lines[id].qr,1);
			}else{ //delete a line from tl<=t<r case then add into tl<=tr<t case
				sum.upd(lines[id].qr,-lines[id].tl);
				num.upd(lines[id].qr,-1);
				f.upd(lines[id].qr,lines[id].tr - lines[id].tl + 1);
			}
		}
		int y = x[1];
		ans[y]+= f.query(n) - f.query(que[y].r-1);
		/*
		if(t==3){
			cout<<f.query(n)<<" "<<f.query(que[y].r-1)<<'\n';
			cout<<que[y].r-1<<" "<<num.query(n)<<" "<<num.query(n) - num.query(que[y].r-1)<<'\n';
		}*/
		ans[y] += (num.query(n) - num.query(que[y].r-1)) * (que[y].t) - (sum.query(n) - sum.query(que[y].r-1));
	}
	for(int i=0;i<=ptr;i++){
		int id = add[i][1];
		sum.reset(lines[id].qr);
		num.reset(lines[id].qr);
		f.reset(lines[id].qr);
	}
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	string s = "0",ss;
	cin>>n>>q>>ss;
	s+=ss;
	
	for(int i=1;i<=n;i++){
		if(s[i] == '0')continue;
		int j = i;
		while(j+1<=n && s[j+1] == '1')j++;
		st[i] = line(0,0,i,j);
		pos.insert(i);
		i = j;
	}
	for(int i=1;i<=q;i++){
		string u;
		cin>>u;
		if(u == "toggle"){
			int x;
			cin>>x;
			if(s[x] == '0'){
				s[x] = '1';
				pos.insert(x);
				st[x] = line(i,i,x,x);
				auto it = pos.upper_bound(x);
				int v = 0;
				if(it != pos.end() && st[*it].ql == x+1){ //new line segment on right side with x as head
					v = *it;
					st[v].tr = i-1; 
					lines.push_back(st[v]);
					//cout<<st[v].tl<<" "<<st[v].tr<<" "<<st[v].ql<<" "<<st[v].qr<<'\n';
					st[x] = line(i,i,x,st[v].qr);
					pos.erase(it);
				}
				it = pos.lower_bound(x);
				if(it == pos.begin())continue;
				it--;
				if(st[*it].qr == x-1){ //new line segment on left side
					v = *it;
					st[v].tr = i-1;
					lines.push_back(st[v]);
					
					int L = st[v].ql;
					st[L] = line(i,i,L,st[x].qr);
					pos.erase(x);
				}
			}else{
				s[x] = '0';
				auto it = pos.upper_bound(x);
				it--;
				int v = *it;

				if(st[v].qr >=x){ //destroy a segment
					st[v].tr = i-1;
					lines.push_back(st[v]);
					
					if(st[v].qr > x){ //line seg on right
						pos.insert(x+1);
						st[x+1] = line(i,i,x+1,st[v].qr);
					}
					if(v != x)st[v] = line(i,i,st[v].ql,x-1); //line seg on left
				}
				pos.erase(x);
			}
		}else{
			int l,r;
			cin>>l>>r;
			que.push_back(qq(l,r-1,i)); cnt++;
			a.push_back({l,-cnt});
		}
		
	}
	for(int i=1;i<=n;i++){
		if(s[i] == '1' && (!i || s[i-1] == '0')){
			st[i].tr = q;
		   	lines.push_back(st[i]);
		}
	}
	for(int i=0;i<sz(lines);i++){
		a.push_back({lines[i].ql,i});
	}
	//for(auto x:lines)cout<<x.tl<<" "<<x.tr<<" "<<x.ql<<" "<<x.qr<<'\n';
	sort(a.begin(),a.end(),[&](array<int,2> i,array<int,2> j){
		if(i[0] == j[0])return j[1] < i[1];
	    return i[0] < j[0];
		}
	);
	sum = fenwick(n);
	num = fenwick(n);
	f = fenwick(n);
	/*
	cout<<"LINES"<<'\n';
	for(auto x:lines)cout<<x.tl<<" "<<x.tr<<" "<<x.ql<<" "<<x.qr<<'\n';
	for(auto x:a)cout<<x[0]<<" "<<x[1]<<'\n';
	* */
	solve(0,sz(a)-1);
	for(int i=0;i<cnt;i++)cout<<ans[i]<<'\n';
}
/*
5 8
01010
toggle 1
toggle 1
toggle 1
toggle 1
query 1 3
toggle 1
query 1 2
query 1 3
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 0 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 12052 KB Output is correct
2 Correct 526 ms 14112 KB Output is correct
3 Correct 656 ms 14928 KB Output is correct
4 Correct 1314 ms 33812 KB Output is correct
5 Correct 1232 ms 33692 KB Output is correct
6 Correct 1307 ms 35388 KB Output is correct
7 Correct 486 ms 24852 KB Output is correct
8 Correct 485 ms 26252 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 999 ms 32808 KB Output is correct
6 Correct 1303 ms 33512 KB Output is correct
7 Correct 1270 ms 31476 KB Output is correct
8 Correct 571 ms 26128 KB Output is correct
9 Correct 209 ms 11708 KB Output is correct
10 Correct 264 ms 13648 KB Output is correct
11 Correct 242 ms 13728 KB Output is correct
12 Correct 560 ms 24720 KB Output is correct
13 Correct 594 ms 26160 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 731 ms 35604 KB Output is correct
6 Correct 1163 ms 33404 KB Output is correct
7 Correct 1116 ms 34616 KB Output is correct
8 Correct 1307 ms 37088 KB Output is correct
9 Correct 487 ms 15644 KB Output is correct
10 Correct 504 ms 18764 KB Output is correct
11 Correct 555 ms 15696 KB Output is correct
12 Correct 541 ms 18708 KB Output is correct
13 Correct 491 ms 15640 KB Output is correct
14 Correct 472 ms 18708 KB Output is correct
15 Correct 569 ms 24760 KB Output is correct
16 Correct 577 ms 26128 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 439 ms 12052 KB Output is correct
9 Correct 526 ms 14112 KB Output is correct
10 Correct 656 ms 14928 KB Output is correct
11 Correct 1314 ms 33812 KB Output is correct
12 Correct 1232 ms 33692 KB Output is correct
13 Correct 1307 ms 35388 KB Output is correct
14 Correct 486 ms 24852 KB Output is correct
15 Correct 485 ms 26252 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 999 ms 32808 KB Output is correct
21 Correct 1303 ms 33512 KB Output is correct
22 Correct 1270 ms 31476 KB Output is correct
23 Correct 571 ms 26128 KB Output is correct
24 Correct 209 ms 11708 KB Output is correct
25 Correct 264 ms 13648 KB Output is correct
26 Correct 242 ms 13728 KB Output is correct
27 Correct 560 ms 24720 KB Output is correct
28 Correct 594 ms 26160 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 3 ms 332 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 2 ms 460 KB Output is correct
33 Correct 731 ms 35604 KB Output is correct
34 Correct 1163 ms 33404 KB Output is correct
35 Correct 1116 ms 34616 KB Output is correct
36 Correct 1307 ms 37088 KB Output is correct
37 Correct 487 ms 15644 KB Output is correct
38 Correct 504 ms 18764 KB Output is correct
39 Correct 555 ms 15696 KB Output is correct
40 Correct 541 ms 18708 KB Output is correct
41 Correct 491 ms 15640 KB Output is correct
42 Correct 472 ms 18708 KB Output is correct
43 Correct 569 ms 24760 KB Output is correct
44 Correct 577 ms 26128 KB Output is correct
45 Correct 216 ms 8536 KB Output is correct
46 Correct 250 ms 8712 KB Output is correct
47 Correct 522 ms 15824 KB Output is correct
48 Correct 1137 ms 33488 KB Output is correct
49 Correct 274 ms 14688 KB Output is correct
50 Correct 307 ms 14680 KB Output is correct
51 Correct 271 ms 14848 KB Output is correct
52 Correct 298 ms 15104 KB Output is correct
53 Correct 342 ms 15080 KB Output is correct
54 Correct 359 ms 15132 KB Output is correct