oj.uz

Submission #478195

# Submission time Handle Problem Language Result Execution time Memory
478195 2021-10-06T11:48:50 Z FatihSolak Mostovi (COI14_mostovi) C++17
100 / 100
 387 ms 11508 KB 
#include <bits/stdc++.h>
#define N 200005
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()){
            if(can(x,prev(bridge[type].lower_bound({y+1,0}))->second,type) && can(prev(bridge[type].lower_bound({y+1,0}))->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;
}
void solve(){
    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";
        }
    }    
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 280 ms 10060 KB Output is correct
8 Correct 357 ms 9920 KB Output is correct
9 Correct 283 ms 11508 KB Output is correct
10 Correct 387 ms 11460 KB Output is correct