| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 966620 |
2024-04-20T06:48:23 Z |
Cookie |
Mostovi (COI14_mostovi) |
C++14 |
|
293 ms |
35416 KB |
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
#define ull unsigned long long
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 19972207, pr = 31;
const int mxn = 5e5 + 5, mxq = 1e5 + 5, sq = 500, mxv = 10005;
//const int base = (1 <<18);
const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
struct DSU{
int op = 0;
int pa[mxn + 1], val[mxn + 1];
void init(int _op){
op = _op;
for(int i = 0; i < mxn; i++){
val[i] = i; pa[i] = -1;
}
}
int fp(int u){
if(pa[u] < 0)return(u);
return(pa[u] = fp(pa[u]));
}
int comb(int a, int b){
if(op == 0)return(max(a, b));
else return(min(a, b));
}
void unon(int u, int v){
u = fp(u); v = fp(v);
if(u == v)return;
if(-pa[u] < -pa[v])swap(u, v);
pa[u] += pa[v]; pa[v] = u;
val[u] = comb(val[u], val[v]);
}
};
struct Q{
char c; int u, v;
};
vt<Q>queries;
int n, m;
DSU mx, mn;
vt<int>comp[2];
map<int, bool>bad;
bool sign(int x){
return(x > n);
}
int find(int x){
int id = sign(x);
return(lower_bound(ALL(comp[id]), x) - comp[id].begin());
}
multiset<pii>up, down;
bool find(int a, int b){
int ida = sign(a), idb = sign(b);
if(ida == 0){
auto it = down.lower_bound(mpp(b, -1));
bool ok = 0;
if(it != down.end()){
int mna = (*it).se;
auto it2 = up.lower_bound(mpp(max(a, mna), -1));
if(it2 != up.end()){
int posb = (*it2).se, posa = (*it2).fi;
//cout << find(b) << " " << mn.val[mn.fp(find(posb))] << " ";
ok = (mn.val[mn.fp(find(posb))] <= find(b) && mx.val[mx.fp(find(a))] >= find(posa));
}
}
return(ok);
}else{
swap(a, b);
auto it = up.lower_bound(mpp(a + 1, -1));
bool ok = 0;
if(it != up.begin()){
--it;
int mxb = (*it).se;
auto it2 = down.lower_bound(mpp(min(b, mxb) + 1, -1));
if(it2 != down.begin()){
--it2;
int posa = (*it2).se, posb = (*it2).fi;
ok = (mn.val[mn.fp(find(b))] <= find(posb) && mx.val[mx.fp(find(posa))] >= find(a));
}
}
return(ok);
}
}
void solve(){
cin >> n >> m;
for(int i = 0; i < m; i++){
char c; cin >> c;
int a, b; cin >> a >> b;
comp[sign(a)].pb(a); comp[sign(b)].pb(b);
queries.pb({c, a, b});
if(a > b)swap(a, b);
if(c == 'B'){
bad[a] = 1;
}else if(c == 'A'){
up.insert(mpp(a, b)); down.insert(mpp(b, a));
}
}
for(int i = 0; i < 2; i++){
sort(ALL(comp[i])); comp[i].resize(unique(ALL(comp[i])) - comp[i].begin());
}
mx.init(0); mn.init(1);
for(int i = 0; i < sz(comp[0]) - 1; i++){
if(!bad[comp[0][i]]){
mx.unon(i, i + 1);
}
}
for(int i = 0; i < sz(comp[1]) - 1; i++){
if(!bad[comp[1][i]]){
mn.unon(i, i + 1);
}
}
vt<bool>res;
reverse(ALL(queries));
for(auto [c, a, b]: queries){
if(c == 'A'){
if(a > b)swap(a, b);
up.erase(up.find(mpp(a, b))); down.erase(down.find(mpp(b, a)));
}else if(c == 'B'){
if(a > b)swap(a, b);
int id = find(a);
if(sign(a) == 0){
mx.unon(id, id + 1);
}else{
mn.unon(id, id + 1);
}
}else{
int ida = sign(a), idb = sign(b);
if(ida == idb){
if(ida == 0){
if(a < b){
res.pb(mx.val[mx.fp(find(a))] >= find(b));
}else{
auto it = up.lower_bound(mpp(a, -1));
if(it == up.end())res.pb(0);
else{
res.pb(find((*it).se, b) && mx.val[mx.fp(find(a))] >= find((*it).fi));
}
}
}else{
if(a > b){
res.pb(mn.val[mn.fp(find(a))] <= find(b));
}else{
auto it = down.lower_bound(mpp(a + 1, -1));
if(it == down.begin())res.pb(0);
else res.pb(find((*prev(it)).se, b) && mn.val[mn.fp(find(a))] <= find((*prev(it)).fi));
}
}
}else{
res.pb(find(a, b));
}
}
}
reverse(ALL(res));
for(auto i: res){
cout << ((i) ? "DA" : "NE") << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("i.inp", "r", stdin);
//freopen("i.out", "w", stdout);
int tt; tt = 1;
while(tt--){
solve();
}
return(0);
}
Compilation message
mostovi.cpp: In function 'bool find(int, int)':
mostovi.cpp:72:24: warning: unused variable 'idb' [-Wunused-variable]
72 | int ida = sign(a), idb = sign(b);
| ^~~
mostovi.cpp: In function 'void solve()':
mostovi.cpp:139:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
139 | for(auto [c, a, b]: queries){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 4 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 5 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 6 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 7 |
Correct |
216 ms |
32680 KB |
Output is correct |
| 8 |
Correct |
229 ms |
31664 KB |
Output is correct |
| 9 |
Correct |
234 ms |
31484 KB |
Output is correct |
| 10 |
Correct |
293 ms |
35416 KB |
Output is correct |
