oj.uz

Submission #447485

# Submission time Handle Problem Language Result Execution time Memory
447485 2021-07-26T14:39:35 Z S2speed Street Lamps (APIO19_street_lamps) C++17
40 / 100
 161 ms 14480 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;
}

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;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 13076 KB Output is correct
2 Correct 96 ms 13088 KB Output is correct
3 Correct 98 ms 13160 KB Output is correct
4 Correct 116 ms 13256 KB Output is correct
5 Correct 120 ms 13488 KB Output is correct
6 Correct 104 ms 13132 KB Output is correct
7 Correct 138 ms 13120 KB Output is correct
8 Correct 161 ms 14480 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 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 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 88 ms 13076 KB Output is correct
9 Correct 96 ms 13088 KB Output is correct
10 Correct 98 ms 13160 KB Output is correct
11 Correct 116 ms 13256 KB Output is correct
12 Correct 120 ms 13488 KB Output is correct
13 Correct 104 ms 13132 KB Output is correct
14 Correct 138 ms 13120 KB Output is correct
15 Correct 161 ms 14480 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Halted 0 ms 0 KB -