oj.uz

Submission #1044649

# Submission time Handle Problem Language Result Execution time Memory
1044649 2024-08-05T12:02:02 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 164 ms 18416 KB 
#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

int main(){
	int n, q;
	cin >> n >> q;
	if(n <= 100 && q <= 100){
		vector<int> v(n);
		string s;
		cin >> s;
		for(int i = 0; i < n; i++) v[i] = (s[i] == '1');

		vector<vector<int>> ans(n, vector<int>(n));
		for(int i = 0; i < q; i++){
			for(int j = 0; j < n; j++){
				for(int k = j; k < n; k++){
					int ok = 1;
					for(int a = j; a <= k; a++)
						ok &= v[a];
					ans[j][k] += ok;
				}
			}
			string t;
			cin >> t;
			if(t == "toggle"){
				int a; cin >> a; a--;
				v[a] ^= 1;
			}
			else{
				int l, r; cin >> l >> r; l--, r-= 2;
				cout << ans[l][r] << endl;
			}
		}
	}
	else{
		vector<int> v(n);
		string s;
		cin >> s;
		for(int i = 0; i < n; i++) v[i] = (s[i] == '1');

		vector<vector<pair<int, int>>> Q(n);
		for(int i = 1; i <= q; i++){
			string t;
			cin >> t;
			if(t == "toggle"){
				int a; cin >> a; a--;
				Q[a].pb({i, 0});
			}
			else{
				int l, r; cin >> l >> r;
				l--, r -= 2;
				Q[l].pb({i, 1});
			}
		}
		vector<int> ans(q + 1, -1);
		for(int i = 0; i < n; i++){
			ll one = v[i];
			ll cev = 0;
			ll time = 0;
			for(auto [a, t] : Q[i]){
				cev += one * (a - time);
				if(t == 0){
					one ^=1;
				}
				else{
					ans[a] = cev;
				}
				time = a;
			}
		}

		for(int i = 0; i <= q; i++){
			if(ans[i] != -1){
				cout << ans[i] << endl;
			}
		}
	}
	

}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 5800 KB Output is correct
2 Correct 92 ms 5636 KB Output is correct
3 Correct 102 ms 6484 KB Output is correct
4 Correct 134 ms 17136 KB Output is correct
5 Correct 140 ms 17656 KB Output is correct
6 Correct 134 ms 16880 KB Output is correct
7 Correct 163 ms 16880 KB Output is correct
8 Correct 164 ms 18416 KB Output is correct

Subtask #3
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 #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 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 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 7 ms 348 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 7 ms 348 KB Output is correct
8 Correct 85 ms 5800 KB Output is correct
9 Correct 92 ms 5636 KB Output is correct
10 Correct 102 ms 6484 KB Output is correct
11 Correct 134 ms 17136 KB Output is correct
12 Correct 140 ms 17656 KB Output is correct
13 Correct 134 ms 16880 KB Output is correct
14 Correct 163 ms 16880 KB Output is correct
15 Correct 164 ms 18416 KB Output is correct
16 Incorrect 1 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -