oj.uz

Submission #478196

# Submission time Handle Problem Language Result Execution time Memory
478196 2021-10-06T11:54:09 Z FatihSolak Mostovi (COI14_mostovi) C++17
80 / 100
 735 ms 11472 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 && y <= *del[type].lower_bound(x))return 1;
        auto it = prev(bridge[type].lower_bound({y+1,0}));
        if(y <= x && bridge[type].size() && bridge[type].lower_bound({y+1,0}) != bridge[type].begin()){
            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
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Runtime error 1 ms 460 KB Execution killed with signal 11
7 Runtime error 1 ms 332 KB Execution killed with signal 11
8 Correct 695 ms 9952 KB Output is correct
9 Correct 549 ms 11408 KB Output is correct
10 Correct 735 ms 11472 KB Output is correct