#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e9;
const int MAXM = 4e5;
int N, M;
int N1, N2;
struct Query
{
char c; int x, y;
};
Query A[MAXM+10];
vector<int> comp1, comp2;
int par[MAXM+10];
int L[MAXM+10], R[MAXM+10];
set<pii> S[MAXM+10];
set<pii> S1, S2;
void init()
{
for(int i=1; i<=MAXM; i++)
{
par[i]=i;
L[i]=R[i]=i;
S[i].clear();
}
}
int Find(int x)
{
if(x==par[x]) return x;
return par[x]=Find(par[x]);
}
void Union(int x, int y)
{
x=Find(x); y=Find(y);
assert(x!=y);
if(S[x].size()>S[y].size()) swap(x, y);
for(auto it : S[x]) S[y].insert(it);
S[x].clear();
par[x]=y;
L[y]=min(L[y], L[x]);
R[y]=max(R[x], R[y]);
}
bool solve(int s, int e)
{
//printf("SOLVE %d %d\n", s, e);
if(s<=N1 && e>N1)
{
int u=Find(s), v=Find(e);
if(S[u].empty()) return false;
auto it=S[u].lower_bound(pii(L[v], 0));
auto jt=S[u].lower_bound(pii(R[v], 2e9));
if(it==jt) return false;
jt--;
int l1, r1, l2, r2;
l1=it->second; r1=jt->second;
l2=it->first; r2=jt->first;
if(r1<s) return false;
if(r2<e) return false;
return true;
}
if(s>N1 && e<=N1)
{
int u=Find(s), v=Find(e);
if(S[u].empty()) return false;
auto it=S[u].lower_bound(pii(L[v], 0));
auto jt=S[u].lower_bound(pii(R[v], 2e9));
if(it==jt) return false;
jt--;
int l1, r1, l2, r2;
l1=it->second; r1=jt->second;
l2=it->first; r2=jt->first;
if(s<l1) return false;
if(e<l2) return false;
return true;
}
if(s<=N1 && e<=N1)
{
int u=Find(s), v=Find(e);
if(u<v) return false;
if(u>v)
{
if(S[u].empty()) return false;
int it=S[u].begin()->first;
return solve(s, it) && solve(it, e);
}
if(u==v)
{
if(s<e) return true;
auto it=S2.lower_bound(pii({s, 0}));
auto jt=S2.lower_bound(pii({e, 2e9}));
if(it==S2.end()) return false;
if(jt==S2.begin()) return false;
jt--;
if(Find(it->first)!=u) return false;
if(Find(jt->first)!=u) return false;
if(Find(it->second)==Find(jt->second)) return true;
else return false;
}
}
if(s>N1 && e>N1)
{
//printf("HI\n");
int u=Find(s), v=Find(e);
if(u>v) return false;
if(u<v)
{
if(S[u].empty()) return false;
int it=(--S[u].end())->first;
//printf("%d\n", it);
return solve(s, it) && solve(it, e);
}
if(u==v)
{
if(s>e) return true;
auto it=S1.lower_bound(pii({e, 0}));
auto jt=S1.lower_bound(pii({s, 2e9}));
if(it==S1.end()) return false;
if(jt==S1.begin()) return false;
jt--;
if(Find(it->first)!=u) return false;
if(Find(jt->first)!=u) return false;
if(Find(it->second)==Find(jt->second)) return true;
else return false;
}
}
}
int chk[MAXM+10];
int main()
{
scanf("%d%d", &N, &M);
for(int i=1; i<=M; i++)
{
scanf(" %c%d%d", &A[i].c, &A[i].x, &A[i].y);
if(A[i].x<=N) comp1.push_back(A[i].x);
else comp2.push_back(A[i].x);
if(A[i].y<=N) comp1.push_back(A[i].y);
else comp2.push_back(A[i].y);
if(A[i].c!='Q' && A[i].x>A[i].y) swap(A[i].x, A[i].y);
}
sort(comp1.begin(), comp1.end());
comp1.erase(unique(comp1.begin(), comp1.end()), comp1.end());
sort(comp2.begin(), comp2.end());
comp2.erase(unique(comp2.begin(), comp2.end()), comp2.end());
N1=comp1.size();
N2=comp2.size();
for(int i=1; i<=M; i++)
{
if(A[i].x<=N) A[i].x=lower_bound(comp1.begin(), comp1.end(), A[i].x)-comp1.begin()+1;
else A[i].x=lower_bound(comp2.begin(), comp2.end(), A[i].x)-comp2.begin()+1+N1;
if(A[i].y<=N) A[i].y=lower_bound(comp1.begin(), comp1.end(), A[i].y)-comp1.begin()+1;
else A[i].y=lower_bound(comp2.begin(), comp2.end(), A[i].y)-comp2.begin()+1+N1;
}
init();
for(int i=1; i<=M; i++)
{
if(A[i].c=='B')
{
chk[A[i].x]++;
}
if(A[i].c=='A')
{
S[A[i].x].insert({A[i].y, A[i].x});
S[A[i].y].insert({A[i].x, A[i].y});
S1.insert({A[i].y, A[i].x});
S2.insert({A[i].x, A[i].y});
}
}
for(int i=1; i<=N1+N2; i++)
{
if(i==N1) continue;
if(i==N1+N2) continue;
if(chk[i]) continue;
Union(i, i+1);
}
vector<int> ans;
for(int i=M; i>=1; i--)
{
//printf("DONE %d\n", i);
if(A[i].c=='A')
{
assert(A[i].x<=N1);
assert(A[i].y>N1);
S[Find(A[i].x)].erase({A[i].y, A[i].x});
S[Find(A[i].y)].erase({A[i].x, A[i].y});
S1.erase({A[i].y, A[i].x});
S2.erase({A[i].x, A[i].y});
}
if(A[i].c=='B')
{
assert(A[i].x+1==A[i].y);
Union(A[i].x, A[i].y);
}
if(A[i].c=='Q')
{
if(solve(A[i].x, A[i].y)) ans.push_back(1);
else ans.push_back(0);
}
}
reverse(ans.begin(), ans.end());
for(auto it : ans)
{
if(it) printf("DA\n");
else printf("NE\n");
}
}
Compilation message
mostovi.cpp: In function 'bool solve(int, int)':
mostovi.cpp:65:7: warning: variable 'l1' set but not used [-Wunused-but-set-variable]
65 | int l1, r1, l2, r2;
| ^~
mostovi.cpp:65:15: warning: variable 'l2' set but not used [-Wunused-but-set-variable]
65 | int l1, r1, l2, r2;
| ^~
mostovi.cpp:80:11: warning: variable 'r1' set but not used [-Wunused-but-set-variable]
80 | int l1, r1, l2, r2;
| ^~
mostovi.cpp:80:19: warning: variable 'r2' set but not used [-Wunused-but-set-variable]
80 | int l1, r1, l2, r2;
| ^~
mostovi.cpp:137:1: warning: control reaches end of non-void function [-Wreturn-type]
137 | }
| ^
mostovi.cpp: In function 'int main()':
mostovi.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
143 | scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
mostovi.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
146 | scanf(" %c%d%d", &A[i].c, &A[i].x, &A[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
20 ms |
23788 KB |
Output is correct |
| 3 |
Correct |
19 ms |
23916 KB |
Output is correct |
| 4 |
Correct |
19 ms |
23916 KB |
Output is correct |
| 5 |
Correct |
19 ms |
23916 KB |
Output is correct |
| 6 |
Correct |
19 ms |
23788 KB |
Output is correct |
| 7 |
Correct |
380 ms |
39312 KB |
Output is correct |
| 8 |
Correct |
602 ms |
40664 KB |
Output is correct |
| 9 |
Correct |
317 ms |
36184 KB |
Output is correct |
| 10 |
Correct |
709 ms |
45696 KB |
Output is correct |
