oj.uz

Submission #966618

# Submission time Handle Problem Language Result Execution time Memory
966618 2024-04-20T06:46:48 Z iliaaaaa Street Lamps (APIO19_street_lamps) C++14
40 / 100
 5000 ms 38764 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 = 1000;
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;
}

Compilation message

street_lamps.cpp: In function 'void ADD(int)':
street_lamps.cpp:81:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |  for (auto [l, r]: SEG[x])
      |            ^
street_lamps.cpp: In function 'void RM(int)':
street_lamps.cpp:86:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |  for (auto [l, r]: SEG[x])
      |            ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 3 ms 14824 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 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 149 ms 27644 KB Output is correct
2 Correct 159 ms 27644 KB Output is correct
3 Correct 234 ms 27644 KB Output is correct
4 Correct 317 ms 34728 KB Output is correct
5 Correct 284 ms 36944 KB Output is correct
6 Correct 340 ms 33308 KB Output is correct
7 Correct 196 ms 29004 KB Output is correct
8 Correct 210 ms 38764 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 10 ms 14684 KB Output is correct
3 Correct 9 ms 14780 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Execution timed out 5090 ms 33928 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 8 ms 14684 KB Output is correct
3 Correct 10 ms 14860 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 1327 ms 33336 KB Output is correct
6 Execution timed out 5012 ms 32084 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 3 ms 14824 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 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 149 ms 27644 KB Output is correct
9 Correct 159 ms 27644 KB Output is correct
10 Correct 234 ms 27644 KB Output is correct
11 Correct 317 ms 34728 KB Output is correct
12 Correct 284 ms 36944 KB Output is correct
13 Correct 340 ms 33308 KB Output is correct
14 Correct 196 ms 29004 KB Output is correct
15 Correct 210 ms 38764 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 10 ms 14684 KB Output is correct
18 Correct 9 ms 14780 KB Output is correct
19 Correct 4 ms 12636 KB Output is correct
20 Execution timed out 5090 ms 33928 KB Time limit exceeded
21 Halted 0 ms 0 KB -