Submission #966613

#	Time	Username	Problem	Language	Result	Execution time	Memory
966613		Cookie	Mostovi (COI14_mostovi)	C++14	30 / 100	253 ms	36084 KiB

mostovi

#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));
                    }
                }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));
                    }
                }
            }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 (stderr)

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){
      |              ^

• Subtask 1: 30 / 100