#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]+1, 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();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |