oj.uz

Submission #966619

# Submission time Handle Problem Language Result Execution time Memory
966619 2024-04-20T06:47:30 Z iliaaaaa Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 39336 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 = 750;
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) {
	int l1 = a.F.F, r1 = a.F.S;
	int l2 = b.F.F, r2 = b.F.S;
	if (l1 / SQ != l2 / SQ)
		return l1 / SQ < l2 / SQ;
	if ((l1 / SQ) % 2)
		return r1 > r2;
	return r1 < r2;
}

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 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 28928 KB Output is correct
2 Correct 169 ms 27532 KB Output is correct
3 Correct 242 ms 29024 KB Output is correct
4 Correct 319 ms 33560 KB Output is correct
5 Correct 278 ms 37204 KB Output is correct
6 Correct 337 ms 33276 KB Output is correct
7 Correct 193 ms 29320 KB Output is correct
8 Correct 201 ms 39336 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 7 ms 14684 KB Output is correct
3 Correct 9 ms 14684 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Execution timed out 5087 ms 33772 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB Output is correct
2 Correct 7 ms 14684 KB Output is correct
3 Correct 9 ms 14860 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 1358 ms 32392 KB Output is correct
6 Execution timed out 5019 ms 32012 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 154 ms 28928 KB Output is correct
9 Correct 169 ms 27532 KB Output is correct
10 Correct 242 ms 29024 KB Output is correct
11 Correct 319 ms 33560 KB Output is correct
12 Correct 278 ms 37204 KB Output is correct
13 Correct 337 ms 33276 KB Output is correct
14 Correct 193 ms 29320 KB Output is correct
15 Correct 201 ms 39336 KB Output is correct
16 Correct 3 ms 14680 KB Output is correct
17 Correct 7 ms 14684 KB Output is correct
18 Correct 9 ms 14684 KB Output is correct
19 Correct 3 ms 12636 KB Output is correct
20 Execution timed out 5087 ms 33772 KB Time limit exceeded
21 Halted 0 ms 0 KB -