oj.uz

Submission #727141

# Submission time Handle Problem Language Result Execution time Memory
727141 2023-04-20T05:28:05 Z SanguineChameleon Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 136276 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[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.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 45 ms 94268 KB Output is correct
2 Correct 44 ms 94180 KB Output is correct
3 Correct 51 ms 94200 KB Output is correct
4 Correct 46 ms 94156 KB Output is correct
5 Correct 42 ms 94276 KB Output is correct
6 Correct 43 ms 94200 KB Output is correct
7 Correct 45 ms 94172 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 101180 KB Output is correct
2 Correct 167 ms 101036 KB Output is correct
3 Correct 168 ms 101692 KB Output is correct
4 Correct 445 ms 122392 KB Output is correct
5 Correct 430 ms 121440 KB Output is correct
6 Correct 447 ms 123148 KB Output is correct
7 Correct 230 ms 115972 KB Output is correct
8 Correct 257 ms 117532 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94284 KB Output is correct
2 Correct 44 ms 94384 KB Output is correct
3 Correct 51 ms 94284 KB Output is correct
4 Correct 45 ms 94340 KB Output is correct
5 Correct 598 ms 124728 KB Output is correct
6 Correct 664 ms 127896 KB Output is correct
7 Correct 612 ms 130676 KB Output is correct
8 Execution timed out 5071 ms 134112 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94404 KB Output is correct
2 Correct 50 ms 94404 KB Output is correct
3 Correct 47 ms 94296 KB Output is correct
4 Correct 50 ms 94336 KB Output is correct
5 Correct 329 ms 136276 KB Output is correct
6 Correct 425 ms 131480 KB Output is correct
7 Correct 491 ms 129240 KB Output is correct
8 Correct 638 ms 126608 KB Output is correct
9 Correct 373 ms 108172 KB Output is correct
10 Correct 321 ms 105584 KB Output is correct
11 Correct 299 ms 107884 KB Output is correct
12 Correct 339 ms 105160 KB Output is correct
13 Correct 301 ms 107968 KB Output is correct
14 Correct 326 ms 105476 KB Output is correct
15 Correct 302 ms 134768 KB Output is correct
16 Execution timed out 5030 ms 133256 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94268 KB Output is correct
2 Correct 44 ms 94180 KB Output is correct
3 Correct 51 ms 94200 KB Output is correct
4 Correct 46 ms 94156 KB Output is correct
5 Correct 42 ms 94276 KB Output is correct
6 Correct 43 ms 94200 KB Output is correct
7 Correct 45 ms 94172 KB Output is correct
8 Correct 131 ms 101180 KB Output is correct
9 Correct 167 ms 101036 KB Output is correct
10 Correct 168 ms 101692 KB Output is correct
11 Correct 445 ms 122392 KB Output is correct
12 Correct 430 ms 121440 KB Output is correct
13 Correct 447 ms 123148 KB Output is correct
14 Correct 230 ms 115972 KB Output is correct
15 Correct 257 ms 117532 KB Output is correct
16 Correct 43 ms 94284 KB Output is correct
17 Correct 44 ms 94384 KB Output is correct
18 Correct 51 ms 94284 KB Output is correct
19 Correct 45 ms 94340 KB Output is correct
20 Correct 598 ms 124728 KB Output is correct
21 Correct 664 ms 127896 KB Output is correct
22 Correct 612 ms 130676 KB Output is correct
23 Execution timed out 5071 ms 134112 KB Time limit exceeded
24 Halted 0 ms 0 KB -