oj.uz

Submission #966617

# Submission time Handle Problem Language Result Execution time Memory
966617 2024-04-20T06:46:09 Z iliaaaaa Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 38184 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) {
	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 4 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 27528 KB Output is correct
2 Correct 156 ms 27640 KB Output is correct
3 Correct 252 ms 28672 KB Output is correct
4 Correct 306 ms 33368 KB Output is correct
5 Correct 284 ms 37836 KB Output is correct
6 Correct 320 ms 33524 KB Output is correct
7 Correct 184 ms 29000 KB Output is correct
8 Correct 197 ms 38184 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 6 ms 14680 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 5091 ms 33784 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
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 7 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 1509 ms 32332 KB Output is correct
6 Execution timed out 5059 ms 31932 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 4 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Correct 153 ms 27528 KB Output is correct
9 Correct 156 ms 27640 KB Output is correct
10 Correct 252 ms 28672 KB Output is correct
11 Correct 306 ms 33368 KB Output is correct
12 Correct 284 ms 37836 KB Output is correct
13 Correct 320 ms 33524 KB Output is correct
14 Correct 184 ms 29000 KB Output is correct
15 Correct 197 ms 38184 KB Output is correct
16 Correct 3 ms 14680 KB Output is correct
17 Correct 6 ms 14680 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 5091 ms 33784 KB Time limit exceeded
21 Halted 0 ms 0 KB -