oj.uz

Submission #1044967

# Submission time Handle Problem Language Result Execution time Memory
1044967 2024-08-05T15:12:02 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 73 ms 22604 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";
		}
	}
}

struct segtree {
	int n;
	vector <int> t;
	void init(int size) {
		n = size;
		t.resize(n * 4);
	}
	void update(int v, int l, int r, int ind, int val) {
		if(l == r) {
			t[v] = val;
			return;
		}
		int m = (l + r) / 2;
		if(ind <= m) {
			update(v * 2, l, m, ind, val);
		}
		else {
			update(v * 2 + 1, m + 1, r, ind, val);
		}
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}
	int query(int v, int l, int r, int ql, int qr) {
		if(l >= ql and r <= qr) {
			return t[v];
		}
		int m = (l + r) / 2;
		int ret = 0;
		if(ql <= m) {
			ret = max(ret, query(v * 2, l, m, ql, qr));
		}
		if(qr > m) {
			ret = max(ret, query(v * 2 + 1, m + 1, r, ql, qr));
		}
		return ret;
	}
};

void solve3(int n, int q, string s, vector<array<int, 3> > Q) {
	segtree t;
	t.init(n);
	for(int i = 0; i < n; i++) {
		if(s[i] == '1') t.update(1, 0, n - 1, i, 0);
	}
	for(int i = 1; i <= q; i++) {
		auto [type, a, b] = Q[i - 1];
		if(type == 1) {
			int ind = a;
			ind--;
			t.update(1, 0, n - 1, ind, i);
		}
		else {
			a--, b -= 2;
			cout << i - t.query(1, 0, n - 1, a, b) << "\n";
		}
	}
}

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 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 16568 KB Output is correct
2 Correct 39 ms 17344 KB Output is correct
3 Correct 44 ms 16060 KB Output is correct
4 Correct 55 ms 21124 KB Output is correct
5 Correct 51 ms 22604 KB Output is correct
6 Correct 43 ms 21324 KB Output is correct
7 Correct 62 ms 21168 KB Output is correct
8 Correct 61 ms 22336 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 344 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 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 73 ms 16568 KB Output is correct
9 Correct 39 ms 17344 KB Output is correct
10 Correct 44 ms 16060 KB Output is correct
11 Correct 55 ms 21124 KB Output is correct
12 Correct 51 ms 22604 KB Output is correct
13 Correct 43 ms 21324 KB Output is correct
14 Correct 62 ms 21168 KB Output is correct
15 Correct 61 ms 22336 KB Output is correct
16 Incorrect 1 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -