oj.uz

Submission #308026

# Submission time Handle Problem Language Result Execution time Memory
308026 2020-09-29T22:36:01 Z qiangbao Mostovi (COI14_mostovi) C++
100 / 100
 409 ms 14456 KB 
#include <iostream>
#include <set>

using namespace std;

typedef pair<int, int> pii;

int n, m;
set<int> block;
set<pii> bridge;
set<pii>:: iterator it1, it2, it3;

int x, y;

int diftp(int xx, int yy)
{
    if((xx<=n && yy>n) || (xx>n && yy<=n))
        return 1;
    return 0;
}

int wk1(int xx, int yy);
int wk2(int xx, int yy);
int wk3(int xx, int yy);

int wk1(int xx, int yy)
{
    if(*(block.lower_bound(xx))<yy)
        return 0;
    return 1;
}

int wk2(int xx, int yy)
{
    it3=bridge.lower_bound({xx, 0});
    if(it3->first==2*n+5 || diftp(it3->first, xx) || !wk1(xx, it3->first))
        return 0;
    
    if((yy<it3->second && wk3(it3->second, yy)) || (yy>=it3->second && wk1(it3->second, yy)))
        return 1;
    return 0;
}

int wk3(int xx, int yy)
{
    it1=bridge.lower_bound({xx, 0});
    it2=bridge.lower_bound({yy+1, 0}), it2--;
    if(it1->first==2*n+5 || diftp(it1->first, xx) || !wk1(xx, it1->first))
        return 0;
    if(it2->first==0 || diftp(it2->first, yy) || !wk1(it2->first, yy))
        return 0;
    
    if(wk1(it1->second, it2->second))
        return 1;
    return 0;
}

int main()
{
    ios_base:: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int i;
    
    cin >> n >> m;
    
    block.insert(2*n+5);
    bridge.insert({0, 0});
    bridge.insert({2*n+5, 2*n+5});
    for(i=1;i<=m;i++){
        char com;
        cin >> com >> x >> y;
        if(x>n)
            x=2*n-x+n+1;
        if(y>n)
            y=2*n-y+n+1;
        if(com=='B'){
            block.insert(min(x, y));
        }
        else if(com=='A'){
            bridge.insert({x, y});
            bridge.insert({y, x});
        }
        else{
            if((x<=n && y<=n) || (x>n && y>n)){
                if(x<y){
                    if(wk1(x, y))
                        cout << "DA" << endl;
                    else
                        cout << "NE" << endl;
                }
                else{
                    if(wk3(x, y))
                        cout << "DA" << endl;
                    else
                        cout << "NE" << endl;
                }
            }
            else{
                if(wk2(x, y))
                    cout << "DA" << endl;
                else
                    cout << "NE" << endl;
            }
        }
    }
    
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 407 ms 12280 KB Output is correct
8 Correct 409 ms 12152 KB Output is correct
9 Correct 362 ms 12408 KB Output is correct
10 Correct 405 ms 14456 KB Output is correct