| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1311958 | IvnF | 가로등 (APIO19_street_lamps) | C++20 | 0 ms | 0 KiB |
/**
* APIO 2019 - Street Lamps
* Solution approach: Offline processing with CDQ Divide & Conquer
* Time Complexity: O(Q log^2 N)
*/
#include <bits/stdc++.h>
using namespace std;
// Define specific types for clarity
using ll = long long;
struct Query {
int type; // 0 for update, 1 for query
int x, y; // Coordinates (x = start of path, y = end of path - 1)
int val; // For update: value to add; For query: id of the query
int time; // Time of event
};
// Global variables
const int MAXN = 300005;
int n, q;
string s;
vector<Query> events;
ll ans[MAXN];
int bit[MAXN]; // Binary Indexed Tree (Fenwick Tree)
// BIT Operations
void update_bit(int idx, int val) {
for (; idx <= n; idx += idx & -idx)
bit[idx] += val;
}
int query_bit(int idx) {
int sum = 0;
for (; idx > 0; idx -= idx & -idx)
sum += bit[idx];
return sum;
}
// CDQ Divide and Conquer
// Solves the 2D range sum problem by reducing one dimension (time)
void cdq(int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
cdq(l, mid);
cdq(mid + 1, r);
// Merge step: Process interactions between Left (Updates) and Right (Queries)
// We sort both halves by X-coordinate to process efficienty
vector<Query> left_part, right_part;
for (int i = l; i <= mid; i++) {
if (events[i].type == 0) left_part.push_back(events[i]);
}
for (int i = mid + 1; i <= r; i++) {
if (events[i].type == 1) right_part.push_back(events[i]);
}
sort(left_part.begin(), left_part.end(), [](const Query& a, const Query& b) {
return a.x < b.x;
});
sort(right_part.begin(), right_part.end(), [](const Query& a, const Query& b) {
return a.x < b.x;
});
// Two-pointer sweep
int ptr = 0;
for (const auto& qry : right_part) {
while (ptr < left_part.size() && left_part[ptr].x <= qry.x) {
update_bit(left_part[ptr].y, left_part[ptr].val);
ptr++;
}
ans[qry.val] += query_bit(qry.y);
}
// Cleanup BIT for next steps (rollback changes)
for (int i = 0; i < ptr; i++) {
update_bit(left_part[i].y, -left_part[i].val);
}
}
// Helper to add a rectangle update
// Adds 'v' to rectangle [x1, x2] x [y1, y2]
// Uses difference array concept:
// (x1, y1) += v, (x1, y2+1) -= v, (x2+1, y1) -= v, (x2+1, y2+1) += v
void add_rectangle(int x1, int y1, int x2, int y2, int v, int t) {
if (x1 > x2 || y1 > y2) return;
events.push_back({0, x1, y1, v, t});
events.push_back({0, x1, y2 + 1, -v, t});
events.push_back({0, x2 + 1, y1, -v, t});
events.push_back({0, x2 + 1, y2 + 1, v, t});
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
cin >> n >> q;
cin >> s;
// 1-based indexing for convenience
s = " " + s;
// Store active intervals of ON lamps
// Intervals are stored as {start, end}
set<pair<int, int>> intervals;
// Initialize intervals based on string s
for (int i = 1; i <= n; ++i) {
if (s[i] == '1') {
int j = i;
while (j <= n && s[j] == '1') j++;
intervals.insert({i, j - 1});
i = j - 1;
}
}
int query_count = 0;
for (int i = 1; i <= q; ++i) {
string type;
cin >> type;
if (type == "toggle") {
int idx;
cin >> idx;
int t = i;
if (s[idx] == '1') {
// Turning OFF
// Find the interval containing idx
auto it = intervals.upper_bound({idx, 1e9});
it--;
int L = it->first;
int R = it->second;
intervals.erase(it);
// Add positive time (Credit) to the