#include <bits/stdc++.h>
using namespace std;
int n;
set<int> del[2];
set<pair<int,int>> bridge[2];
bool can(int x,int y,int type){
if(x > n){
return can(2*n+1-x,2*n+1-y,!type);
}
if(y <= n){
if(x <= y && y <= *del[type].lower_bound(x))return 1;
if(y <= x && bridge[type].size() && bridge[type].lower_bound({y+1,0}) != bridge[type].begin()){
auto it = prev(bridge[type].lower_bound({y+1,0}));
if(can(x,it->second,type) && can(it->first,y,type))return 1;
}
}
else{
if(!(bridge[type].empty() || bridge[type].rbegin()->first < x || bridge[type].rbegin()->second < y)){
int l = x,r = bridge[type].rbegin()->first;
while(l < r){
int m = (l + r)/2;
auto it = bridge[type].lower_bound({m,0});
if(it->second < y){
l = m+1;
}
else r = m;
}
auto it = bridge[type].lower_bound({l,0});
if(can(x,it->first,type)&&can(it->second,y,type))return 1;
}
}
return 0;
}
int main(){
int m;
cin >> n >> m;
del[0].insert(2*n+5);
del[1].insert(2*n+5);
while(m--){
char type;
int x,y;
cin >> type >> x >> y;
if(type == 'A'){
if(y < x)swap(x,y);
bridge[0].insert({x,y});
bridge[1].insert({2*n+1 -y,2*n+1-x});
}
if(type == 'B'){
if(y < x)swap(x,y);
del[0].insert(x);
del[1].insert(2*n+1-y);
}
if(type == 'Q'){
cout << (can(x,y,0)?"DA":"NE") << "\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
204 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
551 ms |
9840 KB |
Output is correct |
| 8 |
Correct |
695 ms |
9856 KB |
Output is correct |
| 9 |
Correct |
562 ms |
11504 KB |
Output is correct |
| 10 |
Correct |
644 ms |
11412 KB |
Output is correct |
