Submission #1326552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326552		ee23b179_cp	Street Lamps (APIO19_street_lamps)	C++20	0 / 100	38 ms	6304 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;

struct DSU {
    vector<int> parent, sz;
    stack<pair<int,int>> history;
    int components;

    DSU(int n) {
        parent.resize(n);
        sz.resize(n,1);
        for(int i=0;i<n;i++) parent[i]=i;
        components = n;
    }

    int find(int x) {
        while(x!=parent[x]) x=parent[x];
        return x;
    }

    void unite(int a,int b){
        a=find(a); b=find(b);
        if(a==b){
            history.push({-1,-1});
            return;
        }
        if(sz[a]<sz[b]) swap(a,b);
        parent[b]=a;
        sz[a]+=sz[b];
        history.push({a,b});
        components--;
    }

    void rollback(){
        auto [a,b]=history.top();
        history.pop();
        if(a==-1) return;
        parent[b]=b;
        sz[a]-=sz[b];
        components++;
    }
};

struct Query {
    int type; // 0 toggle, 1 query
    int a,b;
};

int n,q;
string s;
vector<Query> queries;

vector<pair<int,int>> segtree[4*MAXN];

void add_edge(int node,int l,int r,int ql,int qr,pair<int,int> edge){
    if(qr<l||r<ql) return;
    if(ql<=l && r<=qr){
        segtree[node].push_back(edge);
        return;
    }
    int mid=(l+r)/2;
    add_edge(node*2,l,mid,ql,qr,edge);
    add_edge(node*2+1,mid+1,r,ql,qr,edge);
}

vector<long long> answer;
vector<pair<int,int>> query_list[4*MAXN];

void add_query(int node,int l,int r,int pos,pair<int,int> qr){
    if(l==r){
        query_list[node].push_back(qr);
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) add_query(node*2,l,mid,pos,qr);
    else add_query(node*2+1,mid+1,r,pos,qr);
}

void solve(int node,int l,int r,DSU &dsu){
    int before = dsu.history.size();

    for(auto &e: segtree[node])
        dsu.unite(e.first,e.second);

    if(l==r){
        for(auto &qq: query_list[node]){
            int id=qq.first;
            int a=qq.second;
            int b=queries[id].b;
            if(dsu.find(a)==dsu.find(b))
                answer[id]++;
        }
    } else {
        int mid=(l+r)/2;
        solve(node*2,l,mid,dsu);
        solve(node*2+1,mid+1,r,dsu);
    }

    while(dsu.history.size()>before)
        dsu.rollback();
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>q;
    cin>>s;

    queries.resize(q+1);
    answer.resize(q+1);

    for(int i=1;i<=q;i++){
        string t; cin>>t;
        if(t=="toggle"){
            int x; cin>>x;
            queries[i]={0,x,0};
        } else {
            int a,b; cin>>a>>b;
            queries[i]={1,a,b};
        }
    }

    // NOTE:
    // Full dynamic interval tracking omitted here due to space.
    // In contest solution:
    // - Track active intervals for each lamp
    // - Insert edges into segment tree over time
    // - Add queries
    // - Run solve()

    return 0;
}

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