oj.uz

Submission #727143

# Submission time Handle Problem Language Result Execution time Memory
727143 2023-04-20T05:29:26 Z SanguineChameleon Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 136372 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);
		assert(y >= 1 && y <= n);
		a.push_back({{x, y}, val});
	}

	int get(int x, int y) {
		assert(x >= 1 && x <= n);
		assert(y >= 0 && y <= 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 52 ms 94228 KB Output is correct
2 Correct 48 ms 94176 KB Output is correct
3 Correct 42 ms 94268 KB Output is correct
4 Correct 47 ms 94160 KB Output is correct
5 Correct 42 ms 94264 KB Output is correct
6 Correct 46 ms 94156 KB Output is correct
7 Correct 44 ms 94248 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 101316 KB Output is correct
2 Correct 145 ms 101020 KB Output is correct
3 Correct 189 ms 101688 KB Output is correct
4 Correct 410 ms 122304 KB Output is correct
5 Correct 440 ms 121392 KB Output is correct
6 Correct 430 ms 123244 KB Output is correct
7 Correct 306 ms 115952 KB Output is correct
8 Correct 240 ms 117348 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94284 KB Output is correct
2 Correct 47 ms 94316 KB Output is correct
3 Correct 50 ms 94404 KB Output is correct
4 Correct 45 ms 94276 KB Output is correct
5 Correct 560 ms 124820 KB Output is correct
6 Correct 556 ms 127888 KB Output is correct
7 Correct 477 ms 130792 KB Output is correct
8 Execution timed out 5067 ms 134064 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 94408 KB Output is correct
2 Correct 48 ms 94416 KB Output is correct
3 Correct 46 ms 94324 KB Output is correct
4 Correct 47 ms 94332 KB Output is correct
5 Correct 347 ms 136372 KB Output is correct
6 Correct 409 ms 131600 KB Output is correct
7 Correct 509 ms 129200 KB Output is correct
8 Correct 641 ms 126668 KB Output is correct
9 Correct 320 ms 108184 KB Output is correct
10 Correct 331 ms 105596 KB Output is correct
11 Correct 333 ms 107948 KB Output is correct
12 Correct 325 ms 105232 KB Output is correct
13 Correct 309 ms 107896 KB Output is correct
14 Correct 326 ms 105440 KB Output is correct
15 Correct 335 ms 134772 KB Output is correct
16 Execution timed out 5071 ms 133200 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 94228 KB Output is correct
2 Correct 48 ms 94176 KB Output is correct
3 Correct 42 ms 94268 KB Output is correct
4 Correct 47 ms 94160 KB Output is correct
5 Correct 42 ms 94264 KB Output is correct
6 Correct 46 ms 94156 KB Output is correct
7 Correct 44 ms 94248 KB Output is correct
8 Correct 144 ms 101316 KB Output is correct
9 Correct 145 ms 101020 KB Output is correct
10 Correct 189 ms 101688 KB Output is correct
11 Correct 410 ms 122304 KB Output is correct
12 Correct 440 ms 121392 KB Output is correct
13 Correct 430 ms 123244 KB Output is correct
14 Correct 306 ms 115952 KB Output is correct
15 Correct 240 ms 117348 KB Output is correct
16 Correct 53 ms 94284 KB Output is correct
17 Correct 47 ms 94316 KB Output is correct
18 Correct 50 ms 94404 KB Output is correct
19 Correct 45 ms 94276 KB Output is correct
20 Correct 560 ms 124820 KB Output is correct
21 Correct 556 ms 127888 KB Output is correct
22 Correct 477 ms 130792 KB Output is correct
23 Execution timed out 5067 ms 134064 KB Time limit exceeded
24 Halted 0 ms 0 KB -