oj.uz

Submission #921514

# Submission time Handle Problem Language Result Execution time Memory
921514 2024-02-04T04:26:17 Z LCJLY Street Lamps (APIO19_street_lamps) C++14
20 / 100
 374 ms 69180 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;

inline int combine(int a, int b){
	return a+b;
}

struct node{
	int s,e,m;
	node *l,*r;
	int v;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void upd(int x, int y){
		if(s==e){
			v+=y;
			return;
		}
		if(x<=m)l->upd(x,y);
		else r->upd(x,y);
		v=combine(l->v,r->v);
	}
	
	int query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		if(y<=m)return l->query(x,y);
		if(x>m)return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};

void solve(){
	int n,q;
	cin >> n >> q;
	string s;
	cin >> s;
	s="0"+s+"0";
	
	string temp;
	int l,r;
	vector<pair<pii,int>>que;
	set<pair<pii,int>>se;
	vector<pii>storage[n+5];
	int ptr=0;
	
	for(int x=1;x<=n;x++){
		if(s[x]=='1'){
			int cur=x;
			for(int y=x;y<=n;y++){
				if(s[y]=='0') break;
				cur=y;
			}
			se.insert({{cur,x},0LL});
			x=cur;
		}
	}
	
	//for(auto it:se){
		//show3(l,it.first.second,r,it.first.first,start,it.second);
	//}
	//show(se,1);
	
	for(int x=1;x<=q;x++){
		cin >> temp;
		if(temp=="toggle"){
			cin >> l;
			if(s[l]=='1'){
				//turn off
				auto it=se.lower_bound({{l,0LL},0LL});
				pair<pii,int>hold=*it;
				storage[hold.first.second].push_back({hold.first.first,x-hold.second});
				if(hold.first.second<l){
					se.insert({{l-1,hold.first.second},x});
				}
				if(hold.first.first>l){
					se.insert({{hold.first.first,l+1},x});
				}
				se.erase(se.find(hold));
				s[l]='0';
			}
			else{
				//turn on
				if(s[l-1]=='1'&&s[l+1]=='1'){
					auto it=se.lower_bound({{l,0LL},0LL});
					pair<pii,int>hold,hold2;
					hold=*it;
					it--;
					hold2=*it;
					storage[hold.first.second].push_back({hold.first.first,x-hold.second});
					
					storage[hold2.first.second].push_back({hold2.first.first,x-hold2.second});
					
					se.insert({{hold.first.first,hold2.first.second},x});
					se.erase(se.find(hold));
					se.erase(se.find(hold2));
				}
				else if(s[l-1]=='1'){
					auto it=se.lower_bound({{l,0LL},0LL});
					it--;
					pair<pii,int>hold=*it;
					storage[hold.first.second].push_back({hold.first.first,x-hold.second});
					se.insert({{l,hold.first.second},x});
					se.erase(se.find(hold));
				}
				else if(s[l+1]=='1'){
					auto it=se.lower_bound({{l,0LL},0LL});
					pair<pii,int>hold=*it;
					storage[hold.first.second].push_back({hold.first.first,x-hold.second});
					se.insert({{hold.first.first,l},x});
					se.erase(se.find(hold));
				}
				else{
					se.insert({{l,l},x});
				}
				s[l]='1';
			}
		}
		else{
			cin >> l >> r;
			r--;
			que.push_back({{l,r},ptr++});
		}
		//for(auto it:se){
			//show3(l,it.first.second,r,it.first.first,start,it.second);
		//}
		//show(se,1);
	}
	
	for(auto it:se){
		storage[it.first.second].push_back({it.first.first,q+1-it.second-ptr});
	}
	
	//for(int x=1;x<=n;x++){
		//show(x,x);
		//for(auto it:storage[x]){
			//show2(r,it.first,val,it.second);
		//}
	//}
	
	sort(que.begin(),que.end());
	int ans[ptr];
	
	node st(0,n+5);
	
	int cur=1;
	for(int x=0;x<ptr;x++){
		int lft=que[x].first.first;
		int rgt=que[x].first.second;
		int index=que[x].second;
		while(cur<=lft){
			for(auto it:storage[cur]){
				st.upd(it.first,it.second);
			}
			cur++;
		}
		
		auto it=se.lower_bound({{lft,0LL},0LL});
		pair<pii,int>hold=*it;
		int add=0;
		if(hold.first.second<=lft&&hold.first.first>=rgt){
			add=index;
		}
		ans[index]=st.query(rgt,n)+add;
	}
	
	for(int x=0;x<ptr;x++){
		cout << ans[x] << "\n";
	}
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 344 ms 69180 KB Output is correct
6 Correct 345 ms 67712 KB Output is correct
7 Correct 374 ms 65464 KB Output is correct
8 Correct 364 ms 63888 KB Output is correct
9 Correct 115 ms 13276 KB Output is correct
10 Correct 88 ms 9896 KB Output is correct
11 Correct 114 ms 13056 KB Output is correct
12 Correct 88 ms 9948 KB Output is correct
13 Correct 112 ms 12732 KB Output is correct
14 Correct 89 ms 9896 KB Output is correct
15 Correct 267 ms 62068 KB Output is correct
16 Correct 271 ms 63880 KB Output is correct

Subtask #5
0 / 20.0

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