oj.uz

답안 #478198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
478198 2021-10-06T11:57:50 Z FatihSolak Mostovi (COI14_mostovi) C++17
100 / 100
 756 ms 11436 KB 
#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 && (del[type].lower_bound(x) == del[type].end() || 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; 
    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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 606 ms 9952 KB Output is correct
8 Correct 756 ms 10052 KB Output is correct
9 Correct 527 ms 11428 KB Output is correct
10 Correct 726 ms 11436 KB Output is correct