Submission #447486

#	Time	Username	Problem	Language	Result	Execution time	Memory
447486		S2speed	Street Lamps (APIO19_street_lamps)	C++17	60 / 100	286 ms	23980 KiB

street_lamps

#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<bool , pll> plll;

const ll maxn = 3e5 + 16 , inf = 2e18;

ll n , q;
string s;
vector<plll> qu;
bitset<102> a[102];
ll ans[maxn] , lst[maxn];

void sub1(){
	for(ll i = 0 ; i < n ; i++){
		a[0][i] = (s[i] == '1');
	}
	for(ll i = 1 ; i <= q ; i++){
		string t;
		cin>>t;
		if(t[0] == 'q'){
			a[i] = a[i - 1];
			ll l , r;
			cin>>l>>r; l--; r--;
			ll ans = 0;
			for(ll j = 0 ; j < i ; j++){
				bool ch = true;
				for(ll k = l ; k < r ; k++){
					ch &= a[j][k];
				}
				ans += ch;
			}
			cout<<ans<<'\n';
		} else {
			ll j;
			cin>>j; j--;
			a[i] = a[i - 1];
			a[i][j] = a[i][j] ^ 1;
		}
	}
	return;
}

void sub2(){
	memset(ans , 0 , sizeof(ans));
	memset(lst , -1 , sizeof(lst));
	for(ll i = 0 ; i < n ; i++){
		if(s[i] == '1') lst[i] = 0;
	}
	for(ll i = 1 ; i <= q ; i++){
		bool t = qu[i - 1].first;
		ll j = qu[i - 1].second.first;
		if(t){
			ll res = ans[j];
			if(lst[j] != -1){
				res += i - lst[j];
			}
			cout<<res<<'\n';
		} else {
			if(lst[j] != -1){
				ans[j] += i - lst[j];
				lst[j] = -1;
			} else {
				lst[j] = i;
			}
		}
	}
	return;
}

struct segtree {

	ll sz = 1;
	vector<ll> val;

	void init(ll n){
		while(sz < n) sz <<= 1;
		val.assign(sz << 1 , inf);
		return;
	}

	void set(ll i , ll k , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			val[x] = k;
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		if(i < m){
			set(i , k , ln , lx , m);
		} else {
			set(i , k , rn , m , rx);
		}
		val[x] = max(val[ln] , val[rn]);
		return;
	}

	void set(ll i , ll k){
		set(i , k , 0 , 0 , sz);
		return;
	}

	ll cal(ll l , ll r , ll x , ll lx , ll rx){
		if(rx <= l || lx >= r) return -1;
		if(rx <= r && lx >= l) return val[x];
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		ll a , b;
		a = cal(l , r , ln , lx , m); b = cal(l , r , rn , m , rx);
		return max(a , b);
	}

	ll cal(ll l , ll r){
		return cal(l , r , 0 , 0 , sz);
	}

};

segtree st;

void sub3(){
	st.init(n);
	for(ll i = 0 ; i < n ; i++){
		if(s[i] == '1') st.set(i , 0);
	}
	for(ll i = 1 ; i <= q ; i++){
		bool t = qu[i - 1].first;
		if(t){
			ll l = qu[i - 1].second.first , r = qu[i - 1].second.second , h;
			h = st.cal(l , r);
			if(h == inf){
				cout<<"0\n";
				continue;
			}
			cout<<i - h<<'\n';
		} else {
			ll j = qu[i - 1].second.first;
			st.set(j , i);
		}
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);

	cin>>n>>q>>s;
	if(n <= 1e2 && q <= 1e2){
		sub1();
		return 0;
	}
	bool s2 = true;
	for(ll i = 0 ; i < q ; i++){
		string t;
		cin>>t;
		plll p;
		p.first = (t[0] == 'q');
		if(p.first){
			ll l , r;
			cin>>l>>r; l--; r--;
			s2 &= (r - l == 1);
			p.second = {l , r};
		} else {
			ll j;
			cin>>j; j--;
			p.second = {j , -1};
		}
		qu.push_back(p);
	}
	if(s2){
		sub2();
		return 0;
	}
	sub3();
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20