Submission #63658

#	Time	Username	Problem	Language	Result	Execution time	Memory
63658		chpipis	Port Facility (JOI17_port_facility)	C++11	0 / 100	104 ms	98296 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

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

#define BLUE 0
#define RED 1

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

ii seg[MAXN];
int col[MAXN], who[MAXN * 2];
int st[2][MAXN << 2];
bool exist[MAXN];
vi ds[MAXN << 2];

void ins(params, int i, int j, int val) {
    if (i > R || j < L) return;

    if (i <= L && j >= R) {
        ds[p].pb(val);
        return;
    }

    housekeep;
    ins(left, L, mid, i, j, val);
    ins(right, mid + 1, R, i, j, val);
}

void rec(params, int x, vi &vec) {
    for (auto it : ds[p]) {
        if (exist[it]) vec.pb(it);
        exist[it] = false;
    }
    ds[p].clear();

    if (L == R) return;

    housekeep;

    if (x <= mid)
        rec(left, L, mid, x, vec);
    else
        rec(right, mid + 1, R, x, vec);
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n;
    scanf("%d", &n);
    sz = 2 * n;
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &seg[i].fi, &seg[i].se);
        seg[i].fi--;
        seg[i].se--;
    }
    memset(col, -1, sizeof col);
    sort(seg + 1, seg + n + 1);
    for (int i = 1; i <= n; i++) {
       who[seg[i].fi] = who[seg[i].se] = i;
       exist[i] = true;
       ins(1, 0, 2 * n - 1, seg[i].fi, seg[i].se, i);
    }
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        exist[i] = false;
        if (col[i] == -1) {
            if (query(st[RED], seg[i].fi, seg[i].se) > seg[i].se) {
                col[i] = BLUE;
            } else {
                if (query(st[BLUE], seg[i].fi, seg[i].se) <= seg[i].se) {
                    ans *= 2;
                    while (ans >= MOD) ans -= MOD;
                }
                col[i] = RED;
            }
        }
        /*
        while (proc <= n && seg[proc].fi <= seg[i].fi)
            proc++;
        while (proc <= n && seg[proc].fi <= seg[i].se) {
            active.insert(seg[proc].se);
            proc++;
        }
        if (active.count(seg[i].se)) active.erase(seg[i].se);
        */
        if (query(st[col[i]], seg[i].fi, seg[i].se) > seg[i].se) {
            ans = 0;
            break;
        }
        vi vec;
        rec(1, 0, 2 * n - 1, seg[i].se, vec);
        for (auto it : vec) {
            upd(st[1 - col[i]], seg[it].fi, seg[it].se);
            col[it] = 1 - col[i];
        }
        /*
        if (active.empty()) continue;
        for (auto it = prev(active.end()); *it > seg[i].se; it = prev(it)) {
            upd(st[1 - col[i]], seg[who[*it]].fi, *it);
            col[who[*it]] = 1 - col[i];
            it = active.erase(it);
            if (active.empty()) break;
        }
        */
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
port_facility.cpp:126: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: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22