답안 #727141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727141	2023-04-20T05:28:05 Z	SanguineChameleon	가로등 (APIO19_street_lamps)	C++17	40 / 100	5000 ms	136276 KB

street_lamps

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-