oj.uz

Submission #727132

# Submission time Handle Problem Language Result Execution time Memory
727132 2023-04-20T05:15:05 Z SanguineChameleon Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 135204 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;
	for (int i = 0; i < n; i++) {
		left_query_events.push_back({left_val[i], {1, i}});
	}
	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 55 ms 94156 KB Output is correct
2 Correct 42 ms 94204 KB Output is correct
3 Correct 43 ms 94176 KB Output is correct
4 Correct 42 ms 94260 KB Output is correct
5 Correct 45 ms 94272 KB Output is correct
6 Correct 53 ms 94212 KB Output is correct
7 Correct 44 ms 94288 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 101276 KB Output is correct
2 Correct 139 ms 100964 KB Output is correct
3 Correct 227 ms 101756 KB Output is correct
4 Correct 415 ms 122360 KB Output is correct
5 Correct 452 ms 121420 KB Output is correct
6 Correct 474 ms 123288 KB Output is correct
7 Correct 215 ms 115964 KB Output is correct
8 Correct 233 ms 117288 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 52 ms 94272 KB Output is correct
3 Correct 48 ms 94384 KB Output is correct
4 Correct 47 ms 94360 KB Output is correct
5 Correct 561 ms 124676 KB Output is correct
6 Correct 744 ms 127492 KB Output is correct
7 Correct 637 ms 130072 KB Output is correct
8 Execution timed out 5036 ms 133840 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94280 KB Output is correct
2 Correct 43 ms 94376 KB Output is correct
3 Correct 43 ms 94364 KB Output is correct
4 Correct 42 ms 94284 KB Output is correct
5 Correct 308 ms 135204 KB Output is correct
6 Correct 384 ms 130496 KB Output is correct
7 Correct 541 ms 128728 KB Output is correct
8 Correct 590 ms 126548 KB Output is correct
9 Correct 278 ms 107800 KB Output is correct
10 Correct 272 ms 105408 KB Output is correct
11 Correct 266 ms 107492 KB Output is correct
12 Correct 265 ms 105068 KB Output is correct
13 Correct 259 ms 107440 KB Output is correct
14 Correct 262 ms 105392 KB Output is correct
15 Correct 302 ms 133608 KB Output is correct
16 Execution timed out 5041 ms 132900 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94156 KB Output is correct
2 Correct 42 ms 94204 KB Output is correct
3 Correct 43 ms 94176 KB Output is correct
4 Correct 42 ms 94260 KB Output is correct
5 Correct 45 ms 94272 KB Output is correct
6 Correct 53 ms 94212 KB Output is correct
7 Correct 44 ms 94288 KB Output is correct
8 Correct 140 ms 101276 KB Output is correct
9 Correct 139 ms 100964 KB Output is correct
10 Correct 227 ms 101756 KB Output is correct
11 Correct 415 ms 122360 KB Output is correct
12 Correct 452 ms 121420 KB Output is correct
13 Correct 474 ms 123288 KB Output is correct
14 Correct 215 ms 115964 KB Output is correct
15 Correct 233 ms 117288 KB Output is correct
16 Correct 43 ms 94284 KB Output is correct
17 Correct 52 ms 94272 KB Output is correct
18 Correct 48 ms 94384 KB Output is correct
19 Correct 47 ms 94360 KB Output is correct
20 Correct 561 ms 124676 KB Output is correct
21 Correct 744 ms 127492 KB Output is correct
22 Correct 637 ms 130072 KB Output is correct
23 Execution timed out 5036 ms 133840 KB Time limit exceeded
24 Halted 0 ms 0 KB -