oj.uz

Submission #727134

# Submission time Handle Problem Language Result Execution time Memory
727134 2023-04-20T05:20:21 Z SanguineChameleon Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 136392 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;
	}
/*	cout << cnt << '\n';
	for (int i = 0; i < cnt; i++) {
		cout << right_diff[i] << " ";
	}
	cout << '\n';
	cout << '\n';*/
	
	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 50 ms 94156 KB Output is correct
2 Correct 42 ms 94268 KB Output is correct
3 Correct 43 ms 94184 KB Output is correct
4 Correct 42 ms 94180 KB Output is correct
5 Correct 42 ms 94288 KB Output is correct
6 Correct 43 ms 94156 KB Output is correct
7 Correct 43 ms 94160 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 101260 KB Output is correct
2 Correct 155 ms 101084 KB Output is correct
3 Correct 171 ms 101736 KB Output is correct
4 Correct 457 ms 122360 KB Output is correct
5 Correct 435 ms 121508 KB Output is correct
6 Correct 444 ms 123304 KB Output is correct
7 Correct 227 ms 115980 KB Output is correct
8 Correct 228 ms 117432 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94368 KB Output is correct
2 Correct 43 ms 94380 KB Output is correct
3 Correct 47 ms 94420 KB Output is correct
4 Correct 46 ms 94420 KB Output is correct
5 Correct 638 ms 124724 KB Output is correct
6 Correct 602 ms 127900 KB Output is correct
7 Correct 467 ms 130708 KB Output is correct
8 Execution timed out 5048 ms 134116 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 94352 KB Output is correct
2 Correct 42 ms 94324 KB Output is correct
3 Correct 46 ms 94328 KB Output is correct
4 Correct 44 ms 94284 KB Output is correct
5 Correct 339 ms 136392 KB Output is correct
6 Correct 389 ms 131564 KB Output is correct
7 Correct 524 ms 129212 KB Output is correct
8 Correct 636 ms 126668 KB Output is correct
9 Correct 306 ms 108164 KB Output is correct
10 Correct 324 ms 105568 KB Output is correct
11 Correct 327 ms 107952 KB Output is correct
12 Correct 323 ms 105220 KB Output is correct
13 Correct 302 ms 107924 KB Output is correct
14 Correct 314 ms 105568 KB Output is correct
15 Correct 301 ms 134712 KB Output is correct
16 Execution timed out 5064 ms 133172 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94156 KB Output is correct
2 Correct 42 ms 94268 KB Output is correct
3 Correct 43 ms 94184 KB Output is correct
4 Correct 42 ms 94180 KB Output is correct
5 Correct 42 ms 94288 KB Output is correct
6 Correct 43 ms 94156 KB Output is correct
7 Correct 43 ms 94160 KB Output is correct
8 Correct 143 ms 101260 KB Output is correct
9 Correct 155 ms 101084 KB Output is correct
10 Correct 171 ms 101736 KB Output is correct
11 Correct 457 ms 122360 KB Output is correct
12 Correct 435 ms 121508 KB Output is correct
13 Correct 444 ms 123304 KB Output is correct
14 Correct 227 ms 115980 KB Output is correct
15 Correct 228 ms 117432 KB Output is correct
16 Correct 44 ms 94368 KB Output is correct
17 Correct 43 ms 94380 KB Output is correct
18 Correct 47 ms 94420 KB Output is correct
19 Correct 46 ms 94420 KB Output is correct
20 Correct 638 ms 124724 KB Output is correct
21 Correct 602 ms 127900 KB Output is correct
22 Correct 467 ms 130708 KB Output is correct
23 Execution timed out 5048 ms 134116 KB Time limit exceeded
24 Halted 0 ms 0 KB -