oj.uz

Submission #966615

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 27528 KB Output is correct
2 Correct 157 ms 28412 KB Output is correct
3 Correct 242 ms 28928 KB Output is correct
4 Correct 311 ms 33364 KB Output is correct
5 Correct 274 ms 37052 KB Output is correct
6 Correct 314 ms 33380 KB Output is correct
7 Correct 189 ms 28240 KB Output is correct
8 Correct 195 ms 38484 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 14936 KB Output is correct
3 Correct 5 ms 14684 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct
5 Execution timed out 5017 ms 33764 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 14684 KB Output is correct
2 Correct 5 ms 14784 KB Output is correct
3 Correct 6 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 1923 ms 32336 KB Output is correct
6 Execution timed out 5043 ms 32044 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 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14680 KB Output is correct
4 Correct 3 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 12636 KB Output is correct
8 Correct 148 ms 27528 KB Output is correct
9 Correct 157 ms 28412 KB Output is correct
10 Correct 242 ms 28928 KB Output is correct
11 Correct 311 ms 33364 KB Output is correct
12 Correct 274 ms 37052 KB Output is correct
13 Correct 314 ms 33380 KB Output is correct
14 Correct 189 ms 28240 KB Output is correct
15 Correct 195 ms 38484 KB Output is correct
16 Correct 3 ms 14680 KB Output is correct
17 Correct 5 ms 14936 KB Output is correct
18 Correct 5 ms 14684 KB Output is correct
19 Correct 3 ms 12632 KB Output is correct
20 Execution timed out 5017 ms 33764 KB Time limit exceeded
21 Halted 0 ms 0 KB -