Submission #478197

#	Time	Username	Problem	Language	Result	Execution time	Memory
478197		FatihSolak	Mostovi (COI14_mostovi)	C++17	100 / 100	695 ms	11504 KiB

mostovi

#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";
        }
    }    
}

• Subtask 1: 100 / 100