답안 #745590

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745590 2023-05-20T14:14:42 Z lukadupli Mostovi (COI14_mostovi) C++14
100 / 100
393 ms 14296 KB
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

typedef pair<int, int> pii;

int n, m;

set<int> blok1, blok2;
set<pii> most1, most2;

void most(int a, int b){
    if(a > n) swap(a, b);

    most1.insert({a, b});
    most2.insert({b, a});
}
void blok(int a, int b){
    assert(abs(a - b) == 1);

    if(a > b) swap(a, b);

    if(a <= n) blok1.insert(a);
    else blok2.insert(a);
}

bool upit_ista(int a, int b){
    if(a == b) return 1;
    if(a <= n && b <= n){
        if(a > b) return 0;

        auto lb = blok1.lower_bound(a);
        return lb == blok1.end() || *lb >= b;
    }
    if(a > n && b > n){
        if(a < b) return 0;

        auto lb = blok2.lower_bound(b);
        return lb == blok2.end() || *lb >= a;
    }

    return 0;
}
bool upit(int a, int b){
    if(a <= n && b <= n){
        if(a < b) return upit_ista(a, b);

        if(most1.empty()) return 0;

        auto ptr = most1.lower_bound({a, -1});
        if(ptr == most1.end() || !upit_ista(a, ptr->f)) return 0;

        a = ptr->s;
    }
    if(a > n && b > n){
        if(a > b) return upit_ista(a, b);

        if(most1.empty()) return 0;

        auto ptr = most2.lower_bound({a, 2e9});
        if(ptr == most2.begin()) return 0;
        ptr--;
        if(!upit_ista(a, ptr->f)) return 0;

        a = ptr->s;
    }

    if(most1.empty()) return 0;

    if(a < b){
        auto ptr1 = most1.lower_bound({a, -1});
        auto ptr2 = most2.lower_bound({b, -1});

        if(ptr1 == most1.end() || ptr2 == most2.end()) return 0;
        return (upit_ista(a, ptr1->f) && upit_ista(ptr1->s, b)) || (upit_ista(a, ptr2->s) && upit_ista(ptr2->f, b));
    }

    swap(a, b);

    auto ptr1 = most1.lower_bound({a, 2e9});
    auto ptr2 = most2.lower_bound({b, 2e9});

    if(ptr1 == most1.begin() || ptr2 == most2.begin()) return 0;

    ptr1--; ptr2--;

    return (upit_ista(b, ptr1->s) && upit_ista(ptr1->f, a)) || (upit_ista(b, ptr2->f) && upit_ista(ptr2->s, a));
}

int main()
{
    cin >> n >> m;
    while(m--){
        char c;
        int a, b;
        cin >> c >> a >> b;

        if(c == 'A') most(a, b);
        else if(c == 'B') blok(a, b);
        else cout << (upit(a, b) ? "DA" : "NE") << '\n';
    }

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 316 KB Output is correct
7 Correct 385 ms 12016 KB Output is correct
8 Correct 393 ms 11980 KB Output is correct
9 Correct 340 ms 12076 KB Output is correct
10 Correct 385 ms 14296 KB Output is correct