oj.uz

Submission #447486

# Submission time Handle Problem Language Result Execution time Memory
447486 2021-07-26T14:49:16 Z S2speed Street Lamps (APIO19_street_lamps) C++17
60 / 100
 286 ms 23980 KB 
#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.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 13008 KB Output is correct
2 Correct 105 ms 13028 KB Output is correct
3 Correct 95 ms 13044 KB Output is correct
4 Correct 115 ms 13164 KB Output is correct
5 Correct 122 ms 13460 KB Output is correct
6 Correct 98 ms 13032 KB Output is correct
7 Correct 152 ms 13092 KB Output is correct
8 Correct 146 ms 14512 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 126 ms 16148 KB Output is correct
6 Correct 188 ms 16372 KB Output is correct
7 Correct 211 ms 21652 KB Output is correct
8 Correct 284 ms 23980 KB Output is correct
9 Correct 95 ms 9768 KB Output is correct
10 Correct 104 ms 15792 KB Output is correct
11 Correct 117 ms 15908 KB Output is correct
12 Correct 286 ms 22568 KB Output is correct
13 Correct 286 ms 23852 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 97 ms 13008 KB Output is correct
9 Correct 105 ms 13028 KB Output is correct
10 Correct 95 ms 13044 KB Output is correct
11 Correct 115 ms 13164 KB Output is correct
12 Correct 122 ms 13460 KB Output is correct
13 Correct 98 ms 13032 KB Output is correct
14 Correct 152 ms 13092 KB Output is correct
15 Correct 146 ms 14512 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 126 ms 16148 KB Output is correct
21 Correct 188 ms 16372 KB Output is correct
22 Correct 211 ms 21652 KB Output is correct
23 Correct 284 ms 23980 KB Output is correct
24 Correct 95 ms 9768 KB Output is correct
25 Correct 104 ms 15792 KB Output is correct
26 Correct 117 ms 15908 KB Output is correct
27 Correct 286 ms 22568 KB Output is correct
28 Correct 286 ms 23852 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Incorrect 1 ms 332 KB Output isn't correct
31 Halted 0 ms 0 KB -