oj.uz

Submission #197826

# Submission time Handle Problem Language Result Execution time Memory
197826 2020-01-23T14:09:29 Z TAISA_ Street Lamps (APIO19_street_lamps) C++14
20 / 100
 3 ms 376 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using vi=vector<ll>;
using P=pair<int,int>;
struct Segtree{
	
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,q;cin>>n>>q;
	if(n>100||q>100){
		return 0;
	}
	string str;cin>>str;
	int b=-1;
	set<pair<P,int>> st;
	for(int i=0;i<n;i++){
		if(str[i]=='1'){
			if(b==-1){
				b=i;
			}
		}else{
			if(b!=-1){
				st.insert(mp(P(b,i-1),-1));
				b=-1;
			}
		}
	}
	if(b!=-1){
		st.insert(mp(P(b,n-1),-1));
	}
	vector<pair<P,P>> v;
	for(int i=0;i<q;i++){
		string t;cin>>t;
		if(t=="toggle"){
			int a;cin>>a;--a;
			auto add=[&](pair<P,int> p){
				st.erase(p);
				v.emplace_back(p.first,P(p.second,i));
			};
			auto ins=[&](pair<P,int> p){
				if(p.first.first<=p.first.second){
					st.insert(p);
				}
			};
			if(str[a]=='0'){
				str[a]='1';
				pair<P,int> to=mp(P(a,a),i);
				if(st.empty()){
					ins(to);
					continue;
				}
				auto ir=st.lower_bound(to);
				if(ir!=st.end()&&(*ir).first.first==a+1){
					to.first.second=(*ir).first.second;
					add(*ir);
				}
				auto il=st.lower_bound(to);
				if(il!=st.begin()){
					--il;
					if((*il).first.second==a-1){
						to.first.first=(*il).first.first;
						add(*il);
					}
				}
				ins(to);
			}else{
				str[a]='0';
				auto it=prev(st.lower_bound(mp(P(a+1,-1),-1)));
				pair<P,int> p=(*it);
				add(*it);
				ins(mp(P(p.first.first,a-1),i));
				ins(mp(P(a+1,p.first.second),i));
			}
		}else{
			int a,b;cin>>a>>b;--a;--b;--b;
			auto it=st.lower_bound(mp(P(a+1,-1),-1));
			int res=0;
			if(!st.empty()&&it!=st.begin()){
				--it;
				if((*it).first.first<=a&&b<=(*it).first.second){
					//cout<<(*it).first.first<<" "<<(*it).first.second<<" "<<(*it).second<<" "<<i<<endl;
					res+=i-(*it).second;
				}
			}
			for(auto &e:v){
				if(e.first.first<=a&&b<=e.first.second){
				//	cout<<e.second.first<<" "<<e.second.second<<endl;
					res+=e.second.second-e.second.first;
				}
			}
			cout<<res<<'\n';
		}	
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Incorrect 2 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -