Submission #1311959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311959		IvnF	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	785 ms	60768 KiB

street_lamps

/**
 * 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);

    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 rectangle that is breaking
                // Rectangle: x in [L, idx], y in [idx, R]
                // Query (a, b) maps to x=a, y=b-1. 
                // So valid queries are L <= a <= idx AND idx <= b-1 <= R
                // => L <= a <= idx AND idx+1 <= b <= R+1
                // Correct mapping: Query is (a, b). We map to (a, b-1).
                // Range [L, R] supports query (a, b) if L <= a and b-1 <= R.
                // The toggle breaks support for queries where a <= idx and b-1 >= idx.
                // Bounds: a in [L, idx], b-1 in [idx, R]
                add_rectangle(L, idx, idx, R, t, t);
                
                // Insert split intervals
                if (L <= idx - 1) intervals.insert({L, idx - 1});
                if (idx + 1 <= R) intervals.insert({idx + 1, R});
                
                s[idx] = '0';
            } else {
                // Turning ON
                int L = idx, R = idx;
                
                // Check if we can merge with left
                auto it = intervals.lower_bound({idx, -1}); // first element >= idx
                
                // Check right neighbor
                if (it != intervals.end() && it->first == idx + 1) {
                    R = it->second;
                    it = intervals.erase(it); // Remove right, we will merge
                }
                
                // Check left neighbor
                if (it != intervals.begin()) {
                    it--;
                    if (it->second == idx - 1) {
                        L = it->first;
                        intervals.erase(it);
                    }
                }
                
                intervals.insert({L, R});
                
                // Subtract current time (Debit) from the new rectangle formed
                // Bounds: a in [L, idx], b-1 in [idx, R]
                add_rectangle(L, idx, idx, R, -t, t);
                
                s[idx] = '1';
            }
        } else {
            int a, b;
            cin >> a >> b;
            int t = i;
            // Query map to (a, b-1)
            int y = b - 1;
            
            // 1. Add accumulated history from CDQ
            events.push_back({1, a, y, query_count, t});
            
            // 2. Check if currently valid (Active Asset)
            // If valid, add current time 't' manually
            auto it = intervals.upper_bound({a, 1e9});
            bool active = false;
            if (it != intervals.begin()) {
                it--;
                if (it->first <= a && it->second >= y) {
                    active = true;
                }
            }
            
            if (active) {
                ans[query_count] += t;
            }
            
            query_count++;
        }
    }

    // Run CDQ
    cdq(0, events.size() - 1);

    for (int i = 0; i < query_count; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20