Submission #1234378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234378		kaltspielerhy	Street Lamps (APIO19_street_lamps)	C++20	0 / 100	0 ms	328 KiB

street_lamps

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

struct UnionFind {
    int N;
    vector<int> parents;
    vector<vector<pair<int, int>>> personnal;

    UnionFind(int _N) {
        N = _N;
        parents.assign(N, -1);
        personnal.resize(N);
    }

    int Find(int noeud) {
        if (parents[noeud] == -1) return noeud;
        int result = Find(parents[noeud]);
        parents[noeud] = result;
        return result;
    }

    void Union(int noeud1, int noeud2) {
        parents[noeud2] = Find(noeud1);
    }

    int indexPersonnal(int noeud, int obj) {
        if (personnal[noeud].size() == 0 || personnal[noeud][personnal[noeud].size()-1].first < obj) return -1;

        int deb = 0, fin = personnal[noeud].size()-1;

        while (deb < fin) {
            int mid = (deb+fin)/2;

            if (personnal[noeud][mid].first > obj) {
                fin = mid;
            }
            if (personnal[noeud][mid].first == obj) return personnal[noeud][mid].second;
            if (personnal[noeud][mid].first < obj) {
                deb = mid+1;
            }
        }

        return personnal[noeud][deb].second;
    }
};

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

    int N, Q;
    cin >> N >> Q;
    cin.ignore();
    string elements;
    getline(cin, elements);
    UnionFind journaux(N);
    vector<int> listeIndices;
    for (int i = N-1; i >= 0; i--) {
        if (elements[i] == '0') {
            if (!listeIndices.empty()) {
                for (int i2 = 0; i2 < listeIndices.size()-1; i2++) {
                    journaux.Union(listeIndices[listeIndices.size()-1], listeIndices[i2]);
                }
                journaux.personnal[listeIndices[listeIndices.size()-1]].push_back({listeIndices[0]+1, 0});
                listeIndices.clear();
            }
        }
        else {
            listeIndices.push_back(i);
        }
    }

    if (!listeIndices.empty()) {
        for (int i2 = 0; i2 < listeIndices.size()-1; i2++) {
            journaux.Union(listeIndices[listeIndices.size()-1], listeIndices[i2]);
        }
        journaux.personnal[listeIndices[listeIndices.size()-1]].push_back({listeIndices[0], 0});
        listeIndices.clear();
    }

    for (int i = 1; i <= Q; i++) {
        // for (int i : journaux.parents) cout << i << ' ';
        // cout << '\n';
        string type;
        cin >> type;
        if (type == "toggle") {
            int num;
            cin >> num;
            num--;
            if (num != 0 && elements[num-1] == '1') {
                journaux.Union(num-1, num);
                if (num != N-1 && elements[num+1] == '1') {
                    journaux.Union(num-1, num+1);
                    journaux.personnal[journaux.Find(num-1)].push_back({journaux.personnal[num+1][journaux.personnal[num+1].size()-1].first, i});
                }
                else {
                    journaux.personnal[journaux.Find(num-1)].push_back({num+1, i});
                }
            }
            else if (num != N-1 && elements[num+1] == '1') {
                journaux.Union(num, num+1);
                journaux.personnal[num].push_back({journaux.personnal[num+1][journaux.personnal[num+1].size()-1].first, i});
            }
            else {
                journaux.personnal[num].push_back({num+1, i});
            }
            elements[num] = '1';
        }
        else {
            int a, b;
            cin >> a >> b;
            a--; b--;

            int result1 = journaux.indexPersonnal(a, b);
            if (result1 != -1) {
                cout << i-result1 << '\n';
            } else {
                // cerr << journaux.Find(a) << ' ' << b << '\n';
                int result2 = journaux.indexPersonnal(journaux.Find(a), b);
                cout << (result2 == -1 ? 0 : i-result2) << '\n';
            }
        }
        cin.ignore();
    }
}

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