oj.uz

Submission #1044952

# Submission time Handle Problem Language Result Execution time Memory
1044952 2024-08-05T15:02:57 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 62 ms 22896 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;

void solve1(int n, int q, string s, vector<array<int, 3> > Q) {
	vector <string> states;
	states.push_back(s);
	for(int i = 0; i < q; i++) {
		auto [t, a, b] = Q[i];
		if(t == 2) {
			int ans = 0;
			for(auto it:states) {
				bool yes = 1;
				for(int i = a - 1; i < b - 1; i++) {
					if(it[i] != '1') {
						yes = 0;
						break;
					}
				}
				ans += yes;
			}
			states.push_back(states.back());
			cout << ans << "\n";
		}
		else {
			int ind = a;
			string p = states.back();
			p[ind - 1] = (p[ind - 1] - '0' + 1) % 2 + '0';
			states.push_back(p);
		}
	}
}

void solve2(int n, int q, string s, vector<array<int, 3> > Q) {
	vector <int> till(n, -1), ans(n); // till[ind] = 0 means closed
	for(int i = 0; i < n; i++) {
		if(s[i] == '1') till[i] = 0;
	}
	for(int i = 1; i <= q; i++) {
		auto [t, a, b] = Q[i - 1];
		if(t == 1) {
			int ind = a;
			ind--;
			if(~till[ind]) {
				ans[ind] += i - till[ind];
				till[ind] = -1;
			}
			else {
				till[ind] = i;
			}
		}
		else {
			a--, b-=2;
			int tmp = (~till[a]) ? i - till[a] : 0;
			cout << tmp + ans[a] << "\n";
		}
	}
}

void solve3(int n, int q, string s, vector<array<int, 3> > Q) {
	
}

int32_t main(){
	fast
	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	vector <array<int, 3> > queries;
	bool yes = 0;
	for(int i = 0; i < q; i++) {
		string type;
		cin >> type;
		if(type == "toggle") {
			int ind;
			cin >> ind;
			queries.push_back({1, ind, 0});
		}
		else {
			int a, b;
			cin >> a >> b;
			if(b - a > 1) yes = 1;
			queries.push_back({2, a, b});
		}
	}
	if(!yes) {
		solve2(n, q, s, queries);
	}
	else if(n <= 100 and q <= 100) {
		solve1(n, q, s, queries);
	}
	else {
		solve3(n, q, s, queries);
	}
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 17268 KB Output is correct
2 Correct 40 ms 16968 KB Output is correct
3 Correct 48 ms 16572 KB Output is correct
4 Correct 50 ms 21832 KB Output is correct
5 Correct 62 ms 22180 KB Output is correct
6 Correct 45 ms 20304 KB Output is correct
7 Correct 58 ms 22096 KB Output is correct
8 Correct 58 ms 22896 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 39 ms 17268 KB Output is correct
9 Correct 40 ms 16968 KB Output is correct
10 Correct 48 ms 16572 KB Output is correct
11 Correct 50 ms 21832 KB Output is correct
12 Correct 62 ms 22180 KB Output is correct
13 Correct 45 ms 20304 KB Output is correct
14 Correct 58 ms 22096 KB Output is correct
15 Correct 58 ms 22896 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -