#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define repeat(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define p push
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define vii vector<vector<int>>
#define vi vector<int>
//#define DEBUG
//#define multipletest
using namespace std;
const int LIM=5e5;
const int mod=1e9+7;
const int maxn=20;
const int inf=1e9;
int n,m,x,y,k,t,e,q;
int dx[8]={1,-1,0,0,-1,-1,1,1};
int dy[8]={0,0,-1,1,1,-1,1,-1};
char c;
string s;
int a[LIM+5],factorial[(1<<maxn)+5],inv_fact[(1<<maxn)+5];
bool notprime[LIM+5];
map<int,int> mp;
char grid[100+5][100+5];
set<pair<int,int>> sx,sy;
set<int> del;
int power(int a,int b){
if(b==0) return 1;
int t=power(a,b/2);
t = t * t %mod;
if(b%2==1) t = t * a %mod;
return t;
}
class DSU{
int *parent;
int *rank;
int *tot;
public:
DSU(int n){
rank=new int[n+5];
parent=new int[n+5];
tot=new int [n+5];
for(int i=0;i<n+5;i++){
parent[i]=i;
rank[i]=0;
tot[i]=1;
}
}
int find(int i){
if(parent[i]==i){
return i;
}
return parent[i]=find(parent[i]);
}
void unite(int u,int v){
int i=find(u);
int j=find(v);
if(i!=j){
if(rank[i]>rank[j]){
parent[j]=i;
tot[i]+=tot[j];
}
else if(rank[i]<rank[j]){
parent[i]=j;
tot[j]+=tot[i];
}
else{
parent[j]=i;
rank[i]++;
tot[i]+=tot[j];
}
}
}
int total(int u){
return tot[u];
}
};
void precal(int n){
factorial[0]=1;
inv_fact[0]=1;
for (int i = 1; i <n; ++i)
{
factorial[i] = factorial[i - 1] * i % mod;
inv_fact[i] = inv_fact[i - 1] * power(i, mod - 2) % mod;
}
}
int choose(int n,int k){
if(k<0 || k>n) return 0;
return factorial[n] * inv_fact[n-k] % mod * inv_fact[k] %mod;
}
void Sieve(){
notprime[0]=notprime[1]=true;
for(int i=2;i<LIM+5;++i){
if(notprime[i]==false){
for(int j=i*i;j<LIM+5;j+=i){
notprime[j]=true;
}
}
}
}
pii getr(int u,int v){
auto it = sx.lower_bound({u,0});
if(it!=sx.end() && ((*it).second>=v)){
return (*it);
}
it= sy.lower_bound({v,0});
if(it!=sy.end() && (*it).second>=u){
return {(*it).second,(*it).first};
}
return {0,0};
}
pii getl(int u,int v){
auto it=sx.lower_bound({u+1,0});
if((it)!=sx.begin()){
it--;
if((*it).second<=v){
return (*it);
}
}
it =sy.lower_bound({v+1,0});
if(it!=sy.begin()){
it--;
if((*it).second<=u){
return {(*it).second,(*it).first};
}
}
return {0,0};
}
bool check(int u,int v){
if(u==0 || v==0) return false;
if(u==v){
return true;
}
if(u<=n && v<=n){
if(u<v){
auto it=del.lower_bound(u);
return (it==del.end())||(*it)>=v;
}
else{
auto m=getr(u,0);
return (check(u,m.f) && check(m.s,v));
}
}
if(u>n && v>n){
if(u>v){
auto it=del.lower_bound(v);
return (it==del.end()) || ((*it)>=u);
}
else{
auto m=getl(n+1,u);
return check(u,m.s) && check(m.f,v);
}
}
if(u<=n){
auto m=getr(u,v);
return check(u,m.f) && check(m.s,v);
}
else{
auto m=getl(v,u);
return check(u,m.s) && check(m.f,v);
}
}
void solve(){
//Sieve();
// precal();
cin>>n>>m;
while(m--){
int u,v;
cin>>c>>u>>v;
if(c=='A'){
if(u>v) swap(u,v);
sx.insert({u,v});
sy.insert({v,u});
}
else if(c=='B'){
if(u>v) swap(u,v);
del.insert(u);
}
else{
cout<<(check(u,v)?"DA":"NE")<<endl;
}
}
}
signed main(){
// freopen(".inp","r",stdin);
// freopen(".out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int test;
test=1;
#ifdef multipletest
cin>>test;
#endif
while(test--){
solve();
#ifdef DEBUG
cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
348 KB |
Output is correct |
| 7 |
Correct |
280 ms |
13696 KB |
Output is correct |
| 8 |
Correct |
273 ms |
13608 KB |
Output is correct |
| 9 |
Correct |
223 ms |
13120 KB |
Output is correct |
| 10 |
Correct |
263 ms |
17008 KB |
Output is correct |
