oj.uz

Submission #265170

# Submission time Handle Problem Language Result Execution time Memory
265170 2020-08-14T13:36:52 Z hanagasumi Street Lamps (APIO19_street_lamps) C++17
20 / 100
 383 ms 18864 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef long double ld;

int inf = 1e9 + 100;
int N = (1 << 19);
vector<int> tree(2 * N, inf);

void upd(int v) {
	if(v == 0) 
		return;
	tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
	upd(v / 2);
}

int get(int v, int l, int r, int vl, int vr) {
	if(r <= vl || vr <= l) 
		return 0;
	if(vl <= l && r <= vr) 
		return tree[v];
	int mid = (l + r) / 2;
	return max(get(v * 2, l, mid, vl, vr), get(v * 2 + 1, mid, r, vl, vr));
}

signed main() {
	#ifdef PC
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, q;
	cin >> n >> q;
	vector<int> ans(n, 0);
	for (int i = 0; i < n; i++) {
		char c;
		cin >> c;
		if(c == '1') {
			tree[N + i] = 0;
			upd((N + i) / 2);
		}
	}
	for (int i = 0; i < q; i++) {
		string s;
		cin >> s;
		if(s == "toggle") {
			int id;
			cin >> id;
			id--;
			tree[N + id] = (i + 1);
			upd((N + id) / 2);
			continue;
		}
		int l, r;
		cin >> l >> r;
		l--, r--;
		int st = get(1, 0, N, l, r);
		if(st == inf) {
			cout << 0 << '\n';
			continue;
		}
		cout << (i + 1) - st << '\n';
	}
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8576 KB Output is correct
2 Correct 5 ms 8576 KB Output is correct
3 Correct 6 ms 8576 KB Output is correct
4 Correct 7 ms 8576 KB Output is correct
5 Correct 129 ms 14792 KB Output is correct
6 Correct 197 ms 15992 KB Output is correct
7 Correct 266 ms 16504 KB Output is correct
8 Correct 351 ms 18864 KB Output is correct
9 Correct 135 ms 12280 KB Output is correct
10 Correct 154 ms 12536 KB Output is correct
11 Correct 161 ms 12792 KB Output is correct
12 Correct 342 ms 17528 KB Output is correct
13 Correct 383 ms 18808 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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