Submission #63665

#	Time	Username	Problem	Language	Result	Execution time	Memory
63665		chpipis	Port Facility (JOI17_port_facility)	C++11	100 / 100	4549 ms	603752 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

#define RED 0
#define BLUE 1

const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9;

int sz;

void upd(int *st, int p, int val) {
    p += sz;
    st[p] = max(st[p], val);
    for (; p > 1; p >>= 1) {
         st[p >> 1] = max(st[p], st[p ^ 1]);
    }
}

int query(int *st, int l, int r) {
    int res = 0;
    l += sz, r += sz;
    for (; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) res = max(res, st[l++]);
        if (!(r & 1)) res = max(res, st[r--]);
    }
    return res;
}

int st[2][MAXN << 2];
ii seg[MAXN];
bool exist[MAXN];
int col[MAXN];
ii st_min[MAXN << 2], st_max[MAXN << 2];

void upd_max(int idx) {
    int p = seg[idx].fi + sz;
    if (st_max[p].fi == seg[idx].se)
        st_max[p] = mp(0, -1);
    else
        st_max[p] = mp(seg[idx].se, idx);
    for (; p > 1; p >>= 1) {
        st_max[p >> 1] = max(st_max[p], st_max[p ^ 1]);
    }
}

void upd_min(int idx) {
    int p = seg[idx].se + sz;
    if (st_min[p].fi == seg[idx].fi)
        st_min[p] = mp(INF, -1);
    else
        st_min[p] = mp(seg[idx].fi, idx);
    for (; p > 1; p >>= 1) {
        st_min[p >> 1] = min(st_min[p], st_min[p ^ 1]);
    }
}

int get_max(int l, int r) {
    l += sz;
    r += sz;
    ii res = mp(0, -1);
    for (; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) res = max(res, st_max[l++]);
        if (!(r & 1)) res = max(res, st_max[r--]);
    }
    return res.se;
}

int get_min(int l, int r) {
    l += sz;
    r += sz;
    ii res = mp(INF, -1);
    for (; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) res = min(res, st_min[l++]);
        if (!(r & 1)) res = min(res, st_min[r--]);
    }
    return res.se;
}

void dfs(int u) {
    int v;
    while ((v = get_max(seg[u].fi, seg[u].se)) != -1) {
        if (seg[v].se <= seg[u].se) break;
        upd_max(v);
        upd_min(v);
        col[v] = BLUE + RED - col[u];
        dfs(v);
    }
    while ((v = get_min(seg[u].fi, seg[u].se)) != -1) {
        if (seg[v].fi >= seg[u].fi) break;
        upd_min(v);
        upd_max(v);
        col[v] = BLUE + RED - col[u];
        dfs(v);
    }
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n;
    scanf("%d", &n);
    sz = 2 * n;
    fill(st_min, st_min + sz * 2, mp(INF, -1));
    fill(st_max, st_max + sz * 2, mp(0, -1));
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &seg[i].fi, &seg[i].se);
        seg[i].fi--;
        seg[i].se--;
        upd_max(i);
        upd_min(i);
    }
    memset(col, -1, sizeof col);
    int ans = 1;
    for (int i = 0; i < n; i++) {
        if (col[i] == -1) {
            ans *= 2;
            if (ans >= MOD) ans -= MOD;
            col[i] = RED;
            upd_max(i);
            upd_min(i);
            dfs(i);
        }
        upd(st[col[i]], seg[i].fi, seg[i].se);
    }
    for (int i = 0; i < n; i++) {
        if (query(st[col[i]], seg[i].fi + 1, seg[i].se) > seg[i].se) {
            ans = 0;
            break;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
port_facility.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &seg[i].fi, &seg[i].se);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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