oj.uz

Submission #727147

# Submission time Handle Problem Language Result Execution time Memory
727147 2023-04-20T05:43:05 Z SanguineChameleon Street Lamps (APIO19_street_lamps) C++17
100 / 100
 707 ms 151912 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct node {
	int pref, suf;
	vector<pair<int, int>> left_events;
	vector<pair<int, int>> right_events;
	vector<pair<int, pair<int, int>>> queries;
};

const int inf = 1e9 + 20;
const int maxN = 3e5 + 20;
int a[maxN];
int res[maxN];
node tr[maxN * 4];
int sum_single[maxN];
int prv_single[maxN];

void add_event(int id, int T) {
	if (tr[id].left_events.empty() || tr[id * 2].suf != tr[id].left_events.back().second) {
		tr[id].left_events.push_back({T, tr[id * 2].suf});
	}
	if (tr[id].right_events.empty() || tr[id * 2 + 1].pref != tr[id].right_events.back().second) {
		tr[id].right_events.push_back({T, tr[id * 2 + 1].pref});
	}
}

void merge(int id, int lt, int rt, int mt, int T) {
	tr[id].pref = tr[id * 2].pref + (tr[id * 2].pref == mt - lt + 1 ? tr[id * 2 + 1].pref : 0);
	tr[id].suf = tr[id * 2 + 1].suf + (tr[id * 2 + 1].suf == rt - mt ? tr[id * 2].suf : 0);
	add_event(id, T);
}

void build(int id, int lt, int rt) {
	if (lt == rt) {
		tr[id].pref = a[lt];
		tr[id].suf = a[lt];
		return;
	}
	int mt = (lt + rt) / 2;
	build(id * 2, lt, mt);
	build(id * 2 + 1, mt + 1, rt);
	merge(id, lt, rt, mt, 0);
}

void update(int id, int lt, int rt, int pos, int T) {
	if (lt == rt) {
		if (a[lt] == 1) {
			sum_single[lt] += T - prv_single[lt];
		}
		prv_single[lt] = T;
		a[lt] ^= 1;
		tr[id].pref = a[lt];
		tr[id].suf = a[lt];
		return;
	}
	int mt = (lt + rt) / 2;
	if (pos <= mt) {
		update(id * 2, lt, mt, pos, T);
	}
	else {
		update(id * 2 + 1, mt + 1, rt, pos, T);
	}
	merge(id, lt, rt, mt, T);
}

void add(int id, int lt, int rt, int ql, int qr, int T) {
	if (lt == rt) {
		res[T] = sum_single[lt];
		if (a[lt] == 1) {
			res[T] += T - prv_single[lt];
		}
		return;
	}
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		add(id * 2, lt, mt, ql, qr, T);
	}
	else if (ql >= mt + 1) {
		add(id * 2 + 1, mt + 1, rt, ql, qr, T);
	}
	else {
		tr[id].queries.push_back({T, {mt - ql + 1, qr - mt}});
	}
}

struct BIT {
	vector<vector<int>> pos;
	vector<vector<int>> bit;
	int n;

	void init1(int _n) {
		n = _n;
		bit.clear();
		bit.resize(n + 1);
		pos.clear();
		pos.resize(n + 1);
	}

	void fupdate(int x, int y) {
		for (int i = x; i <= n; i += i & (-i)) {
			pos[i].push_back(y);
		}
	}

	void init2() {
		for (int i = 1; i <= n; i++) {
			sort(pos[i].begin(), pos[i].end());
			pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
			bit[i].resize(pos[i].size() + 1);
		}
	}

	void update(int x, int y, int val) {
		for (int i = x; i <= n; i += i & (-i)) {
			for (int j = upper_bound(pos[i].begin(), pos[i].end(), y) - pos[i].begin(); j <= (int)pos[i].size(); j += j & (-j)) {
				bit[i][j] += val;
			}
		}
	}

	int get(int x, int y) {
		int res = 0;
		for (int i = x; i > 0; i -= i & (-i)) {
			for (int j = upper_bound(pos[i].begin(), pos[i].end(), y) - pos[i].begin(); j > 0; j -= j & (-j)) {
				res += bit[i][j];
			}
		}
		return res;
	}

} bit;

void solve(int id) {
	vector<pair<int, pair<int, int>>> &queries = tr[id].queries;
	vector<pair<int, int>> &left_events = tr[id].left_events;
	vector<pair<int, int>> &right_events = tr[id].right_events;
	if (queries.empty()) {
		return;
	}
	left_events.push_back({inf, -1});
	right_events.push_back({inf, -1});
	vector<pair<int, pair<int, int>>> events;
	int sz_left = left_events.size();
	int sz_right = right_events.size();
	int sz_queries = queries.size();
	vector<int> left_pos(sz_left);
	vector<int> right_pos(sz_right);
	vector<int> query_pos(sz_queries);
	for (int i = 0; i < sz_left; i++) {
		events.push_back({left_events[i].first, {0, i}});
	}
	for (int i = 0; i < sz_right; i++) {
		events.push_back({right_events[i].first, {1, i}});
	}
	for (int i = 0; i < sz_queries; i++) {
		events.push_back({queries[i].first, {2, i}});
	}
	sort(events.begin(), events.end());
	int n = 0;
	vector<int> len;
	for (int i = 0; i < (int)events.size(); i++) {
		if (i > 0 && events[i].first != events[i - 1].first) {
			len.push_back(events[i].first - events[i - 1].first);
			n++;
		}
		if (events[i].second.first == 0) {
			left_pos[events[i].second.second] = n;
		}
		if (events[i].second.first == 1) {
			right_pos[events[i].second.second] = n;
		}
		if (events[i].second.first == 2) {
			query_pos[events[i].second.second] = n - 1;
		}
	}
	vector<int> left_val(n);
	vector<int> right_val(n);
	for (int i = 0; i < sz_left - 1; i++) {
		for (int j = left_pos[i]; j < left_pos[i + 1]; j++) {
			left_val[j] = left_events[i].second;
		}
	}
	for (int i = 0; i < sz_right - 1; i++) {
		for (int j = right_pos[i]; j < right_pos[i + 1]; j++) {
			right_val[j] = right_events[i].second;
		}
	}
	vector<pair<int, pair<int, int>>> left_query_events;
	vector<pair<int, int>> right_vals;
	for (int i = 0; i < n; i++) {
		left_query_events.push_back({left_val[i], {1, i}});
		right_vals.push_back({-right_val[i], i});
	}
	sort(right_vals.begin(), right_vals.end());
	int cnt = 0;
	vector<int> right_diff;
	for (int i = 0; i < n; i++) {
		if (i == 0 || right_vals[i].first != right_vals[i - 1].first) {
			right_diff.push_back(right_vals[i].first);
			cnt++;
		}
		right_val[right_vals[i].second] = cnt;
	}
	for (int i = 0; i < sz_queries; i++) {
		queries[i].second.second = upper_bound(right_diff.begin(), right_diff.end(), -queries[i].second.second) - right_diff.begin();
	}
	for (int i = 0; i < sz_queries; i++) {
		left_query_events.push_back({queries[i].second.first, {0, i}});
	}
	sort(left_query_events.begin(), left_query_events.end(), greater<>());
	bit.init1(n);
	for (auto e: left_query_events) {
		if (e.second.first == 1) {
			int pos = e.second.second;
			bit.fupdate(pos + 1, right_val[pos]);
		}
	}
	bit.init2();
	for (auto e: left_query_events) {
		if (e.second.first == 1) {
			int pos = e.second.second;
			bit.update(pos + 1, right_val[pos], len[pos]);
		}
		else {
			int id = e.second.second;
			int T = queries[id].first;
			int Y = queries[id].second.second;
			int pos = query_pos[id];
			res[T] = bit.get(pos + 1, Y);
		}
	}
}

void solve(int id, int lt, int rt) {
	if (lt == rt) {
		return;
	}
	solve(id);
	int mt = (lt + rt) / 2;
	solve(id * 2, lt, mt);
	solve(id * 2 + 1, mt + 1, rt);
}

void just_do_it() {
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		a[i] = c - '0';
	}
	build(1, 1, n);
	for (int T = 1; T <= q; T++) {
		res[T] = -1;
		string s;
		cin >> s;
		if (s == "toggle") {
			int pos;
			cin >> pos;
			update(1, 1, n, pos, T);
		}
		if (s == "query") {
			int ql, qr;
			cin >> ql >> qr;
			qr--;
			add(1, 1, n, ql, qr, T);
		}
	}
	solve(1, 1, n);
	for (int i = 1; i <= q; i++) {
		if (res[i] != -1) {
			cout << res[i] << '\n';
		}
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 94168 KB Output is correct
2 Correct 50 ms 94220 KB Output is correct
3 Correct 51 ms 94268 KB Output is correct
4 Correct 47 ms 94256 KB Output is correct
5 Correct 45 ms 94228 KB Output is correct
6 Correct 45 ms 94160 KB Output is correct
7 Correct 46 ms 94188 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 101192 KB Output is correct
2 Correct 161 ms 101032 KB Output is correct
3 Correct 195 ms 101772 KB Output is correct
4 Correct 429 ms 122364 KB Output is correct
5 Correct 458 ms 121516 KB Output is correct
6 Correct 469 ms 123268 KB Output is correct
7 Correct 229 ms 115988 KB Output is correct
8 Correct 229 ms 117384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94340 KB Output is correct
2 Correct 55 ms 94328 KB Output is correct
3 Correct 54 ms 94380 KB Output is correct
4 Correct 52 ms 94400 KB Output is correct
5 Correct 572 ms 124948 KB Output is correct
6 Correct 669 ms 130048 KB Output is correct
7 Correct 673 ms 138604 KB Output is correct
8 Correct 520 ms 149424 KB Output is correct
9 Correct 292 ms 121540 KB Output is correct
10 Correct 327 ms 126244 KB Output is correct
11 Correct 331 ms 123760 KB Output is correct
12 Correct 444 ms 150416 KB Output is correct
13 Correct 531 ms 149484 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94412 KB Output is correct
2 Correct 58 ms 94344 KB Output is correct
3 Correct 61 ms 94280 KB Output is correct
4 Correct 47 ms 94260 KB Output is correct
5 Correct 473 ms 151912 KB Output is correct
6 Correct 586 ms 141752 KB Output is correct
7 Correct 604 ms 133388 KB Output is correct
8 Correct 690 ms 126732 KB Output is correct
9 Correct 583 ms 111880 KB Output is correct
10 Correct 609 ms 106400 KB Output is correct
11 Correct 589 ms 111680 KB Output is correct
12 Correct 690 ms 106352 KB Output is correct
13 Correct 629 ms 111640 KB Output is correct
14 Correct 707 ms 106552 KB Output is correct
15 Correct 523 ms 150368 KB Output is correct
16 Correct 585 ms 148952 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 94168 KB Output is correct
2 Correct 50 ms 94220 KB Output is correct
3 Correct 51 ms 94268 KB Output is correct
4 Correct 47 ms 94256 KB Output is correct
5 Correct 45 ms 94228 KB Output is correct
6 Correct 45 ms 94160 KB Output is correct
7 Correct 46 ms 94188 KB Output is correct
8 Correct 149 ms 101192 KB Output is correct
9 Correct 161 ms 101032 KB Output is correct
10 Correct 195 ms 101772 KB Output is correct
11 Correct 429 ms 122364 KB Output is correct
12 Correct 458 ms 121516 KB Output is correct
13 Correct 469 ms 123268 KB Output is correct
14 Correct 229 ms 115988 KB Output is correct
15 Correct 229 ms 117384 KB Output is correct
16 Correct 48 ms 94340 KB Output is correct
17 Correct 55 ms 94328 KB Output is correct
18 Correct 54 ms 94380 KB Output is correct
19 Correct 52 ms 94400 KB Output is correct
20 Correct 572 ms 124948 KB Output is correct
21 Correct 669 ms 130048 KB Output is correct
22 Correct 673 ms 138604 KB Output is correct
23 Correct 520 ms 149424 KB Output is correct
24 Correct 292 ms 121540 KB Output is correct
25 Correct 327 ms 126244 KB Output is correct
26 Correct 331 ms 123760 KB Output is correct
27 Correct 444 ms 150416 KB Output is correct
28 Correct 531 ms 149484 KB Output is correct
29 Correct 46 ms 94412 KB Output is correct
30 Correct 58 ms 94344 KB Output is correct
31 Correct 61 ms 94280 KB Output is correct
32 Correct 47 ms 94260 KB Output is correct
33 Correct 473 ms 151912 KB Output is correct
34 Correct 586 ms 141752 KB Output is correct
35 Correct 604 ms 133388 KB Output is correct
36 Correct 690 ms 126732 KB Output is correct
37 Correct 583 ms 111880 KB Output is correct
38 Correct 609 ms 106400 KB Output is correct
39 Correct 589 ms 111680 KB Output is correct
40 Correct 690 ms 106352 KB Output is correct
41 Correct 629 ms 111640 KB Output is correct
42 Correct 707 ms 106552 KB Output is correct
43 Correct 523 ms 150368 KB Output is correct
44 Correct 585 ms 148952 KB Output is correct
45 Correct 439 ms 116156 KB Output is correct
46 Correct 425 ms 111208 KB Output is correct
47 Correct 422 ms 118668 KB Output is correct
48 Correct 697 ms 141796 KB Output is correct
49 Correct 339 ms 133544 KB Output is correct
50 Correct 379 ms 133448 KB Output is correct
51 Correct 398 ms 133632 KB Output is correct
52 Correct 363 ms 134392 KB Output is correct
53 Correct 341 ms 134384 KB Output is correct
54 Correct 346 ms 134296 KB Output is correct