oj.uz

Submission #727137

# Submission time Handle Problem Language Result Execution time Memory
727137 2023-04-20T05:23:56 Z SanguineChameleon Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 136356 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<pair<pair<int, int>, int>> a;
	int n;

	void init(int _n) {
		a.clear();
		n = _n;
	}

	void add(int x, int y, int val) {
		assert(x >= 1 && x <= n);
		a.push_back({{x, y}, val});
	}

	int get(int x, int y) {
		assert(x >= 1 && x <= n);
		int res = 0;
		for (auto p: a) {
			if (p.first.first <= x && p.first.second <= y) {
				res += p.second;
			}
		}
		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[id].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.init(n);
	for (auto e: left_query_events) {
		if (e.second.first == 1) {
			int pos = e.second.second;
			bit.add(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 46 ms 94156 KB Output is correct
2 Correct 51 ms 94172 KB Output is correct
3 Correct 49 ms 94280 KB Output is correct
4 Correct 43 ms 94248 KB Output is correct
5 Correct 45 ms 94264 KB Output is correct
6 Correct 43 ms 94220 KB Output is correct
7 Correct 44 ms 94228 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 101260 KB Output is correct
2 Correct 159 ms 100944 KB Output is correct
3 Correct 174 ms 101684 KB Output is correct
4 Correct 436 ms 122304 KB Output is correct
5 Correct 470 ms 121588 KB Output is correct
6 Correct 443 ms 123144 KB Output is correct
7 Correct 223 ms 115948 KB Output is correct
8 Correct 259 ms 117500 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94312 KB Output is correct
2 Correct 44 ms 94304 KB Output is correct
3 Correct 45 ms 94320 KB Output is correct
4 Correct 48 ms 94328 KB Output is correct
5 Correct 533 ms 124796 KB Output is correct
6 Correct 587 ms 127932 KB Output is correct
7 Correct 472 ms 130780 KB Output is correct
8 Execution timed out 5044 ms 134080 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94392 KB Output is correct
2 Correct 52 ms 94412 KB Output is correct
3 Correct 51 ms 94368 KB Output is correct
4 Correct 44 ms 94316 KB Output is correct
5 Correct 321 ms 136356 KB Output is correct
6 Correct 424 ms 131512 KB Output is correct
7 Correct 510 ms 129228 KB Output is correct
8 Correct 651 ms 126652 KB Output is correct
9 Correct 325 ms 108192 KB Output is correct
10 Correct 354 ms 105612 KB Output is correct
11 Correct 358 ms 107952 KB Output is correct
12 Correct 347 ms 105228 KB Output is correct
13 Correct 288 ms 107888 KB Output is correct
14 Correct 324 ms 105516 KB Output is correct
15 Correct 322 ms 134808 KB Output is correct
16 Execution timed out 5063 ms 133260 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94156 KB Output is correct
2 Correct 51 ms 94172 KB Output is correct
3 Correct 49 ms 94280 KB Output is correct
4 Correct 43 ms 94248 KB Output is correct
5 Correct 45 ms 94264 KB Output is correct
6 Correct 43 ms 94220 KB Output is correct
7 Correct 44 ms 94228 KB Output is correct
8 Correct 136 ms 101260 KB Output is correct
9 Correct 159 ms 100944 KB Output is correct
10 Correct 174 ms 101684 KB Output is correct
11 Correct 436 ms 122304 KB Output is correct
12 Correct 470 ms 121588 KB Output is correct
13 Correct 443 ms 123144 KB Output is correct
14 Correct 223 ms 115948 KB Output is correct
15 Correct 259 ms 117500 KB Output is correct
16 Correct 45 ms 94312 KB Output is correct
17 Correct 44 ms 94304 KB Output is correct
18 Correct 45 ms 94320 KB Output is correct
19 Correct 48 ms 94328 KB Output is correct
20 Correct 533 ms 124796 KB Output is correct
21 Correct 587 ms 127932 KB Output is correct
22 Correct 472 ms 130780 KB Output is correct
23 Execution timed out 5044 ms 134080 KB Time limit exceeded
24 Halted 0 ms 0 KB -