제출 #727135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727135		SanguineChameleon	가로등 (APIO19_street_lamps)	C++17	20 / 100	539 ms	123492 KiB

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[id].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: 0 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20