Submission #40833

#	Time	Username	Problem	Language	Result	Execution time	Memory
40833		DoanPhuDuc	Port Facility (JOI17_port_facility)	C++98	0 / 100	48 ms	55160 KiB

port_facility

#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)

using namespace std;

typedef pair <int, int> II;
typedef long long LL;

const int N = 2 * (1e6 + 10);
const int LG = 25;
const int INF = 0x3f3f3f3f;
const int BASE = 1e9 + 7;

int n;
int a[N], L[N], R[N], pos[N], p[N];

bool fre[N];

vector <int> adj[N];

struct Segment {
    int l, r;
    Segment () {}
    Segment (int l, int r) : l(l), r(r) {}
    bool operator < (const Segment &that) const {
        return l < that.l;
    }
} seg[N];

struct DSU {
    int p[N];
    void Init() {
        memset(p, -1, sizeof p);
    }
    int Root(int u) {
        return p[u] < 0 ? u : p[u] = Root(p[u]);
    }
    void Union(int u, int v) {
        u = Root(u); v = Root(v);
        if (u == v) return;
        if (p[u] > p[v]) swap(u, v);
        p[u] += p[v];
        p[v] = u;
    }
} DSU;

set <int> S;

int Find(int v) {
    set <int> :: iterator it = S.lower_bound(v);
    if (it == S.begin()) return -1;
        else return *(--it);
}

struct RMQ {
    int lg[N];
    int spT[2][N][LG];
    void Init() {
        FOR(i, 1, 2 * n) {
            spT[0][i][0] = (a[i] > i ? a[i] : 0);
            spT[1][i][0] = ((a[i] != 0 && a[i] < i) ? a[i] : INF);
        }
        for (int j = 1; 1 << j <= 2 * n; ++j)
            for (int i = 1; i + (1 << j) - 1 <= 2 * n; ++i) {
                spT[0][i][j] = max(spT[0][i][j - 1], spT[0][i + (1 << (j - 1))][j - 1]);
                spT[1][i][j] = min(spT[1][i][j - 1], spT[1][i + (1 << (j - 1))][j - 1]);
            }
        for (int i = 0; 1 << i <= 2 * n; ++i) lg[1 << i] = i;
        FOR(i, 1, 2 * n) if (!lg[i]) lg[i] = lg[i - 1];
    }
    int Query(int t, int l, int r) {
        int k = lg[r - l + 1];
        if (t == 0)return max(spT[t][l][k], spT[t][r - (1 << k) + 1][k]);
            else return min(spT[t][l][k], spT[t][r - (1 << k) + 1][k]);
    }
} RMQ;

bool Intersect(int x, int y) {
    int l1 = L[x], r1 = R[x];
    int l2 = L[y], r2 = R[y];
    if (l2 > r1 || r2 < l1) return false;
    if (l1 < l2 && r2 < r1) return false;
    if (l2 < l1 && r1 < r2) return false;
    return true;
}

bool CMP(int x, int y) {
    if (L[x] != L[y]) return L[x] < L[y];
    return R[x] < R[y];
}

bool cycle = false;

void DFS(int u, int par = -1) {
    DEBUG(u);
    fre[u] = true;
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k]; if (v == par) continue;
        if (fre[v] == false) DFS(v, u);
            else {
                cout << u << " " << v << endl;
                cycle = true;
            }
    }
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d", &n);
    FOR(i, 1, n) {
        int l, r; scanf("%d%d", &l, &r);
        seg[i] = Segment(l, r);
        a[l] = r;
        a[r] = l;
        pos[l] = i;
        pos[r] = i;
    }
    RMQ.Init();
    DSU.Init();
    sort(seg + 1, seg + n + 1);
   // FOR(i, 1, n) cout << seg[i].l << " " << seg[i].r << endl;
    //cout << endl;
    FOR(i, 1, n)
        FOR(j, i + 1, n) if (seg[j].l < seg[i].r && seg[j].r > seg[i].r) {
          //  adj[i].push_back(j);
          //  adj[j].push_back(i);
            int r1 = DSU.Root(i), r2 = DSU.Root(j);
          //  cout << i << " " << j << endl;
            if (r1 != r2) DSU.Union(i, j);
                else {
                    puts("0");
                return 0;

                }
        }
    DSU.Init();
  /*  FOR(timer, 1, 2 * n) {
        assert(a[timer] != 0);
        if (a[timer] > timer) {
            int l2 = timer, r2 = a[timer];
            int r1 = Find(r2);
            if (r1 != -1) {
                if (l2 < r1 && RMQ.Query(0, l2, r1) > r2) {
                    puts("0");
                    return 0;
                }
            }
            S.insert(a[timer]);
        } else {
            S.erase(timer);
        }
    }*/
    int fre = 0;
    FOR(timer, 1, 2 * n) {
        if (a[timer] > timer) {
            int l = timer, r = a[timer];
            int lMin = RMQ.Query(1, l, r), rMax = RMQ.Query(0, l, r);
            if (lMin < l) DSU.Union(pos[timer], pos[lMin]);
            if (rMax > r) DSU.Union(pos[timer], pos[rMax]);
        }
    }
    int cmp = 0;
    FOR(i, 1, n) if (DSU.p[i] < 0) ++cmp;
    int ans = 1;
    FOR(i, 1, cmp) ans = (LL)ans * 2 % BASE;
    cout << ans;
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void DFS(int, int)':
port_facility.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
port_facility.cpp:104:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:163:9: warning: unused variable 'fre' [-Wunused-variable]
     int fre = 0;
         ^
port_facility.cpp:119:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
port_facility.cpp:121:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int l, r; scanf("%d%d", &l, &r);
                                        ^

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