oj.uz

Submission #966609

# Submission time Handle Problem Language Result Execution time Memory
966609 2024-04-20T06:39:14 Z iliaaaaa Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 43752 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define All(x) (x).begin(),(x).end()
#define len(x) (int)(x).size()
#define pb push_back

const int N = 3e5 + 7, SQ = 500;
int n, q, ans[N], lst[N], lazy[N << 2];
vector<pair<pii, int>> qu;
vector<pii> SEG[N];
pii seg[N << 2];
bool on[N];

void build(int id = 1, int st = 0, int en = q) {
	seg[id].S = en - st;
	if (en - st == 1) 
		return;
	int mid = (st + en) >> 1;
	build(id << 1, st, mid);
	build(id << 1 | 1, mid, en);
}

void Apply(int id, int x) {
	seg[id].F += x;
	lazy[id] += x;
}

void shift(int id) {
	Apply(id << 1, lazy[id]);
	Apply(id << 1 | 1, lazy[id]);
	lazy[id] = 0;
}

pii merge(pii a, pii b) {
	if (a.F != b.F)
		return max(a, b);
	return pii(a.F, a.S + b.S);
}

void upd(int l, int r, int x, int id = 1, int st = 0, int en = q) {
	if (r <= st || l >= en)
		return;
	if (st >= l && en <= r) {
		Apply(id, x);
		return;
	}
	shift(id);
	int mid = (st + en) >> 1;
	upd(l, r, x, id << 1, st, mid);
	upd(l, r, x, id << 1 | 1, mid, en);
	seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}

pii get(int l, int r, int id = 1, int st = 0, int en = q) {
	if (r <= st || l >= en)
		return pii(-1, -1);
	if (st >= l && en <= r)
		return seg[id];
	shift(id);
	int mid = (st + en) >> 1;
	return merge(get(l, r, id << 1, st, mid), get(l, r, id << 1 | 1, mid, en));
}

bool cmp(pair<pii, int> a, pair<pii, int> b) {
	return pii(a.F.F / SQ, a.F.S) < pii(b.F.F / SQ, b.F.S);
}

void ADD(int x) {
	for (auto [l, r]: SEG[x])
		upd(l, r + 1, 1);
}

void RM(int x) {
	for (auto [l, r]: SEG[x])
		upd(l, r + 1, -1);
}

int32_t main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string s;
	cin >> n >> q >> s;
	build();
	for (int i = 0; i < n; i++)
		on[i] = (s[i] == '1');
	for (int i = 0; i < q; i++) {
		string s;
		int a, b;
		cin >> s >> a;
		if (s == "query") {
			cin >> b;
			b--;
			qu.pb({{--a, --b}, i});
		}
		else {
			ans[i] = -1;
			a--;
			if (on[a])
				SEG[a].pb({lst[a], i});
			else 
				lst[a] = i + 1;
			on[a] = !on[a];
		}
	}
	for (int i = 0; i < n; i++)
		if (on[i]) 
			SEG[i].pb({lst[i], q - 1});
	sort(All(qu), cmp);
	ADD(0);
	int L = 0, R = 0;
	for (auto p: qu) {
		int idx = p.S, st = p.F.F, en = p.F.S;
		while (R < en)
			ADD(++R);
		while (L > st)
			ADD(--L);
		while (R > en)
			RM(R--);
		while (L < st)
			RM(L++);
		pii res = get(0, idx + 1);
		if (res.F == en - st + 1)
			ans[idx] = res.S;
	}
	for (int i = 0; i < q; i++)
		if (ans[i] != -1)
			cout << ans[i] << '\n';
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 3 ms 14816 KB Output is correct
6 Correct 2 ms 12772 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 30748 KB Output is correct
2 Correct 166 ms 31856 KB Output is correct
3 Correct 199 ms 32624 KB Output is correct
4 Correct 243 ms 38480 KB Output is correct
5 Correct 220 ms 42252 KB Output is correct
6 Correct 243 ms 38304 KB Output is correct
7 Correct 186 ms 35424 KB Output is correct
8 Correct 223 ms 43752 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 7 ms 14684 KB Output is correct
3 Correct 8 ms 14684 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Execution timed out 5056 ms 38176 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB Output is correct
2 Correct 7 ms 14684 KB Output is correct
3 Correct 7 ms 14780 KB Output is correct
4 Correct 4 ms 14684 KB Output is correct
5 Correct 2594 ms 38912 KB Output is correct
6 Execution timed out 5020 ms 37496 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 3 ms 14816 KB Output is correct
6 Correct 2 ms 12772 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 155 ms 30748 KB Output is correct
9 Correct 166 ms 31856 KB Output is correct
10 Correct 199 ms 32624 KB Output is correct
11 Correct 243 ms 38480 KB Output is correct
12 Correct 220 ms 42252 KB Output is correct
13 Correct 243 ms 38304 KB Output is correct
14 Correct 186 ms 35424 KB Output is correct
15 Correct 223 ms 43752 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 7 ms 14684 KB Output is correct
18 Correct 8 ms 14684 KB Output is correct
19 Correct 3 ms 12636 KB Output is correct
20 Execution timed out 5056 ms 38176 KB Time limit exceeded
21 Halted 0 ms 0 KB -