Submission #1117204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117204		ShaShi	Port Facility (JOI17_port_facility)	C++17	100 / 100	4812 ms	961440 KiB

port_facility

#include <bits/stdc++.h>
 
// #define int long long 
 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define pll pair<long long, long long>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
// typedef __int128_t lll;
typedef long double ld;
 
 
const int MAXN = (int)2e6 + 7;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
const int LG = 30;
 
 
int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, N, res, pre_ans;
pii arr[MAXN];
bool seen[MAXN], col[MAXN], st[MAXN];
vector<pair<int, bool>> adj[MAXN];



inline void add_edge(int u, int v, bool x) {
    // cout << "! " << u << " " << v << " " << x << endl;
    adj[u].pb({v, x});
    adj[v].pb({u, x});
}


/* Segment Tree */
#define mid ((l+r)>>1)
#define lid (id<<1)
#define rid (lid|1)


vector<int> seg[MAXN<<2];
int ptr[MAXN<<2];


void add_seg(int s, int x, int l=0, int r=MAXN, int id=1) {
    if (l+1 == r) {
        seg[id].pb(x);
        return;
    }

    if (s < mid) add_seg(s, x, l, mid, lid);
    else add_seg(s, x, mid, r, rid);
}


void build(int l=0, int r=MAXN, int id=1) {
    ptr[id] = -1;

    if (l+1 == r) {
        sort(all(seg[id]));
        return;
    }

    build(l, mid, lid);
    build(mid, r, rid);

    seg[id].resize(seg[lid].size()+seg[rid].size());
    merge(all(seg[lid]), all(seg[rid]), seg[id].begin());
}


void check(int s, int t, int x, int l=0, int r=MAXN, int id=1) {
    if (s >= t) return;

    if (s <= l && t >= r) {
        if (seg[id].empty() || seg[id][0] > x) return;

        add_edge(seg[id][0], x, 1);

        while (ptr[id]+1 < seg[id].size() && seg[id][ptr[id]+1] < x) ptr[id]++;

        return;
    }

    if (s < mid) check(s, t, x, l, mid, lid);
    if (t > mid) check(s, t, x, mid, r, rid);
}


inline void process(int id) {
    for (int i=1; i<=ptr[id]; i++) add_edge(seg[id][0], seg[id][i], 0);
}


void rebuild(int l=0, int r=MAXN, int id=1) {
    if (l+1 == r) {
        process(id);
        return;
    }

    rebuild(l, mid, lid);
    rebuild(mid, r, rid);

    process(id);
}

/* Segment Tree */



void DFS(int v) {
    seen[v] = 1;

    for (auto cur:adj[v]) {
        int u = cur.F, w = cur.S;

        if (!seen[u]) {
            if (w == 1) col[u] = 1-col[v];
            else col[u] = col[v];

            DFS(u);
        } else if ((w == 1 && col[u] == col[v]) || (w == 0 && col[u] != col[v])) kill(0);
    }
}


int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif


    cin >> n;

    for (int i=1; i<=n; i++) {
        cin >> arr[i].F >> arr[i].S;

        st[arr[i].F] = 1; add_seg(arr[i].S, arr[i].F);
    }

    build();

    for (int i=1; i<=n; i++) check(arr[i].F, arr[i].S, arr[i].F);


    rebuild();

    ans = 1;

    for (int i=1; i<MAXN; i++) {
        if (seen[i] || !st[i]) continue;

        DFS(i);

        ans = (ans+ans)%MOD;
    }

    cout << ans << endl;
    
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void check(int, int, int, int, int, int)':
port_facility.cpp:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         while (ptr[id]+1 < seg[id].size() && seg[id][ptr[id]+1] < x) ptr[id]++;
      |                ~~~~~~~~~~^~~~~~~~~~~~~~~~

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