Submission #745590

#	Time	Username	Problem	Language	Result	Execution time	Memory
745590		lukadupli	Mostovi (COI14_mostovi)	C++14	100 / 100	393 ms	14296 KiB

mostovi

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

• Subtask 1: 100 / 100