제출 #87491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87491		tieunhi	Port Facility (JOI17_port_facility)	C++14	100 / 100	3499 ms	374488 KiB

port_facility

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define mid (r + l)/2
#define N 2000005
#define LN 19
#define maxc 1000000007

using namespace std;

int n, pos[N], a[N], dd[N];
pii seg[N];

struct IntervalTree
{
    int tmin[N << 2], tmax[N << 2];

    void calc(int id)
    {
        tmin[id] = min(tmin[id*2], tmin[id*2+1]);
        tmax[id] = max(tmax[id*2], tmax[id*2+1]);
    }
    void build(int l, int r, int id)
    {
        if (l == r)
        {
            tmin[id] = tmax[id] = a[l];
            return;
        }
        build(l, mid, id*2);
        build(mid+1, r, id*2+1);
        calc(id);
    }
    void disable(int l, int r, int id, int x)
    {
        if (l == r)
        {
            tmin[id] = maxc; tmax[id] = 0;
            return;
        }
        if (x <= mid) disable(l, mid, id*2, x);
        else disable(mid+1, r, id*2+1, x);
        calc(id);
    }
    int getMin(int l, int r, int id, int x, int y)
    {
        if (l > y || r < x) return maxc;
        if (l >= x && r <= y) return tmin[id];
        return min(getMin(l, mid, id*2, x, y), getMin(mid+1, r, id*2+1, x, y));
    }
    int getMax(int l, int r, int id, int x, int y)
    {
        if (l > y || r < x) return 0;
        if (l >= x && r <= y) return tmax[id];
        return max(getMax(l, mid, id*2, x, y), getMax(mid+1, r, id*2+1, x, y));
    }
}t;

void stop() {cout <<0; exit(0);}
void DFS(int u, int col)
{
    dd[u] = col;
    t.disable(1, 2*n, 1, seg[u].F);
    t.disable(1, 2*n, 1, seg[u].S);
    while (1)
    {
        int l = t.getMin(1, 2*n, 1, seg[u].F, seg[u].S);
        if (l >= seg[u].F) break;
        int v = pos[l];
        if (dd[v] != -1)
            if (dd[v] != (col^1)) stop();
        DFS(v, col^1);
    }
    while (1)
    {
        int r = t.getMax(1, 2*n, 1, seg[u].F, seg[u].S);
        if (r <= seg[u].S) break;
        int v = pos[r];
        if (dd[v] != -1)
            if (dd[v] != (col^1)) stop();
        DFS(v, col^1);
    }
}
bool check()
{
    stack<int> v[2];
    FOR(i, 1, 2*n)
    {
        int u = pos[i];
        int type = dd[u];
        if (i == seg[u].F) v[type].push(u);
        else
        {
            if (v[type].top() != u) return 0;
            v[type].pop();
        }
    }
    return 1;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n;
    FOR(i, 1, n)
    {
        int u, v; cin >> u >> v;
        seg[i] = mp(u, v);
    }
    sort(seg+1, seg+n+1);
    FOR(i, 1, n)
    {
        int u = seg[i].F, v = seg[i].S;
        a[u] = v; a[v] = u;
        pos[u] = pos[v] = i;
    }
    t.build(1, 2*n, 1);
    memset(dd, -1, sizeof dd);

    int res = 1;
    FOR(i, 1, n)
    {
        if (dd[i] != -1) continue;
        DFS(i, 0);
        res = (res*2) % maxc;
    }
    if (check()) cout <<res;
    else stop();
}

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