oj.uz

Submission #966610

# Submission time Handle Problem Language Result Execution time Memory
966610 2024-04-20T06:40:15 Z iliaaaaa Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 39220 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 = 320;
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 4 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 3 ms 14684 KB Output is correct
5 Correct 4 ms 14684 KB Output is correct
6 Correct 2 ms 12636 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 160 ms 27792 KB Output is correct
2 Correct 199 ms 27536 KB Output is correct
3 Correct 183 ms 28388 KB Output is correct
4 Correct 250 ms 33360 KB Output is correct
5 Correct 244 ms 37468 KB Output is correct
6 Correct 223 ms 33276 KB Output is correct
7 Correct 188 ms 28504 KB Output is correct
8 Correct 206 ms 39220 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 5 ms 14684 KB Output is correct
3 Correct 7 ms 14684 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Execution timed out 5071 ms 34112 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 14684 KB Output is correct
2 Correct 6 ms 14780 KB Output is correct
3 Correct 6 ms 14680 KB Output is correct
4 Correct 3 ms 14680 KB Output is correct
5 Correct 3454 ms 33764 KB Output is correct
6 Execution timed out 5048 ms 31912 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 3 ms 14684 KB Output is correct
5 Correct 4 ms 14684 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 160 ms 27792 KB Output is correct
9 Correct 199 ms 27536 KB Output is correct
10 Correct 183 ms 28388 KB Output is correct
11 Correct 250 ms 33360 KB Output is correct
12 Correct 244 ms 37468 KB Output is correct
13 Correct 223 ms 33276 KB Output is correct
14 Correct 188 ms 28504 KB Output is correct
15 Correct 206 ms 39220 KB Output is correct
16 Correct 3 ms 14680 KB Output is correct
17 Correct 5 ms 14684 KB Output is correct
18 Correct 7 ms 14684 KB Output is correct
19 Correct 3 ms 12636 KB Output is correct
20 Execution timed out 5071 ms 34112 KB Time limit exceeded
21 Halted 0 ms 0 KB -