Submission #93953

#	Time	Username	Problem	Language	Result	Execution time	Memory
93953		Alexa2001	Port Facility (JOI17_port_facility)	C++17	78 / 100	6160 ms	891208 KiB

port_facility

#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

using namespace std;

typedef pair<int,int> Pair;
const int Nmax = 2e6 + 5, Mod = 1e9 + 7;

int col[Nmax], A[Nmax], B[Nmax];
int n;

/// 19:00
class STree
{
    vector<Pair> a[Nmax<<2];

    public:
        void update(int node, int st, int dr, int pos, Pair what)
        {
            a[node].push_back(what);
            if(st == dr) return;

            if(pos <= mid) update(left_son, st, mid, pos, what);
                else update(right_son, mid+1, dr, pos, what);
        }

        void init(int node, int st, int dr)
        {
            sort(a[node].begin(), a[node].end());
            if(st == dr) return;

            init(left_son, st, mid);
            init(right_son, mid+1, dr);
        }

        int query(int node, int st, int dr, int L, int R, int val)
        {
            if(L <= st && dr <= R)
            {
                while(a[node].size() && col[a[node].back().second]) a[node].pop_back();
                if(a[node].size() && a[node].back().first > val)
                    return a[node].back().second;
                return -1;
            }

            int res = -1;
            if(L <= mid) res = query(left_son, st, mid, L, R, val);
            if(res == -1 && mid < R) res = query(right_son, mid+1, dr, L, R, val);
            return res;
        }
} aint1, aint2;

void dfs(int node, int C = 1)
{
    col[node] = C;

    while(1)
    {
        int x = aint1.query(1, 1, 2*n, A[node], B[node], B[node]);
        if(x == -1) break;
        dfs(x, 3 - C);
    }

    while(1)
    {
        int x = aint2.query(1, 1, 2*n, A[node], B[node], -A[node]);
        if(x == -1) break;
        dfs(x, 3 - C);
    }
}

bool check(vector<Pair> &v)
{
    sort(v.begin(), v.end());

    priority_queue< int, vector<int>, greater<int> > heap;
    int i;

    for(i=0; i<v.size(); ++i)
    {
        while(heap.size() && heap.top() < v[i].first) heap.pop();
        if(heap.size() && heap.top() < v[i].second) return 0;
        heap.push(v[i].second);
    }
    return 1;
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i;
    cin >> n;
    for(i=1; i<=n; ++i) cin >> A[i] >> B[i];

    for(i=1; i<=n; ++i)
    {
        aint1.update(1, 1, 2*n, A[i], {B[i], i});
        aint2.update(1, 1, 2*n, B[i], {-A[i], i});
    }

    aint1.init(1, 1, 2*n);
    aint2.init(1, 1, 2*n);

    int ans = 1;
    for(i=1; i<=n; ++i)
        if(!col[i])
        {
            ans = 2 * ans % Mod;
            dfs(i);
        }

    vector<Pair> v[3];
    for(i=1; i<=n; ++i) v[col[i]].push_back({A[i], B[i]});

    if(check(v[1]) && check(v[2])) cout << ans << '\n';
        else cout << 0 << '\n';

    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'bool check(std::vector<std::pair<int, int> >&)':
port_facility.cpp:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v.size(); ++i)
              ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 0 / 22