oj.uz

답안 #839305

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
839305 2023-08-29T15:50:35 Z fanwen Port Facility (JOI17_port_facility) C++17
100 / 100
 1494 ms 195116 KB 
/**
 *      author : pham van sam 
 *      created : 29.08.2023 21:47:12
 **/

#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

#ifdef LOCAL 
    #include "debug.h"
#else 
    #define clog if(false) cerr
#endif

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

const int Mod = 1e9 + 7;

void add(int &x, int y) {
    if((x += y) >= Mod) x -= Mod;
    if(x < 0) x += Mod;
}

template < class T, T (*f) (T, T), T (*e) ()>
struct segment_tree {
    vector <T> tree;
    int n;

    void update(int u, int p) {
        u--;
        for(tree[u += n] += p; u >>= 1; ) {
            tree[u] = f(tree[u << 1], tree[u << 1 | 1]);
        }
    }

    void set(int u, int p) {
        u--;
        for (tree[u += n] = p; u >>= 1; ) {
            tree[u] = f(tree[u << 1], tree[u << 1 | 1]);
        }
    }

    T get(int p) {
        return tree[p += n - 1];
    }

    T get(int l, int r) {
        l--;
        T resl = e(), resr = e();
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) resl = f(resl, tree[l++]);
            if(r & 1) resr = f(tree[--r], resr);
        }
        return f(resl, resr);
    }

    segment_tree(int n = 0) : n(n), tree(n << 2 | 1) {
        fill(tree.begin(), tree.end(), e());
    }
};

namespace _max_ {
    int op(int a, int b) { return a > b ? a : b; }
    int e() { return numeric_limits<int>::min(); }
};

namespace _min_ {
    int op(int a, int b) { return a < b ? a : b; }
    int e() { return numeric_limits<int>::max(); }
};

const int MAXN = 1e6 + 5;

template <class T> using It_Max = segment_tree <T, _max_::op, _max_::e>;
template <class T> using It_Min = segment_tree <T, _min_::op, _min_::e>;

int N, dd[MAXN], pos[2 * MAXN];

struct Segment {
    int l, r;
    Segment(int _l = 0, int _r = 0) : l(_l), r(_r) {}
    bool operator < (const Segment &other) const { return l < other.l || (l == other.l and r < other.r); }
} A[MAXN];

void you_make_it(void) {
    cin >> N;
    FOR(i, 1, N) cin >> A[i].l >> A[i].r;
    sort(A + 1, A + N + 1);
    It_Max <int> itMax(2 * N);
    It_Min <int> itMin(2 * N);
    FOR(i, 1, N) {
        itMin.set(A[i].r, A[i].l);
        itMax.set(A[i].l, A[i].r);
        pos[A[i].l] = pos[A[i].r] = i;
    }
    memset(dd, -1, sizeof dd);

    function <void(int, int)> dfs = [&](int u, int color) {
        if(dd[u] != -1 and dd[u] != color) {
            cout << 0;
            exit(0);
        }
        clog << u << " ";
        dd[u] = color;
        itMax.set(A[u].l, _max_::e());
        itMin.set(A[u].r, _min_::e());

        while(itMax.get(A[u].l, A[u].r) > A[u].r) {
            int i = pos[itMax.get(A[u].l, A[u].r)];
            dfs(i, color ^ 1);
        }

        while(itMin.get(A[u].l, A[u].r) < A[u].l) {
            int i = pos[itMin.get(A[u].l, A[u].r)];
            dfs(i, color ^ 1);
        }
    };
    int ans = 1;
    FOR(i, 1, N) if(dd[i] == -1) {
        dfs(i, 0);
        add(ans, ans);
        clog << endl;
    }
    stack <int> check[2];
    FOR(i, 1, 2 * N) {
        int u = pos[i];
        if(i == A[u].l) check[dd[u]].push(u);
        else {
            if(check[dd[u]].top() != u) {
                cout << 0;
                return;
            }
            check[dd[u]].pop();
        }
    }
    cout << ans;
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
  	file("port_facility");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

port_facility.cpp: In instantiation of 'segment_tree<T, f, e>::segment_tree(int) [with T = int; T (* f)(T, T) = _max_::op; T (* e)() = _max_::e]':
port_facility.cpp:101:29:   required from here
port_facility.cpp:39:9: warning: 'segment_tree<int, _max_::op, _max_::e>::n' will be initialized after [-Wreorder]
   39 |     int n;
      |         ^
port_facility.cpp:38:16: warning:   'std::vector<int> segment_tree<int, _max_::op, _max_::e>::tree' [-Wreorder]
   38 |     vector <T> tree;
      |                ^~~~
port_facility.cpp:69:5: warning:   when initialized here [-Wreorder]
   69 |     segment_tree(int n = 0) : n(n), tree(n << 2 | 1) {
      |     ^~~~~~~~~~~~
port_facility.cpp: In instantiation of 'segment_tree<T, f, e>::segment_tree(int) [with T = int; T (* f)(T, T) = _min_::op; T (* e)() = _min_::e]':
port_facility.cpp:102:29:   required from here
port_facility.cpp:39:9: warning: 'segment_tree<int, _min_::op, _min_::e>::n' will be initialized after [-Wreorder]
   39 |     int n;
      |         ^
port_facility.cpp:38:16: warning:   'std::vector<int> segment_tree<int, _min_::op, _min_::e>::tree' [-Wreorder]
   38 |     vector <T> tree;
      |                ^~~~
port_facility.cpp:69:5: warning:   when initialized here [-Wreorder]
   69 |     segment_tree(int n = 0) : n(n), tree(n << 2 | 1) {
      |     ^~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:18:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:157:4: note: in expansion of macro 'file'
  157 |    file("port_facility");
      |    ^~~~
port_facility.cpp:18:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:157:4: note: in expansion of macro 'file'
  157 |    file("port_facility");
      |    ^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11996 KB Output is correct
2 Correct 5 ms 11996 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 5 ms 11988 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Correct 5 ms 11992 KB Output is correct
7 Correct 5 ms 11988 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 5 ms 11988 KB Output is correct
10 Correct 5 ms 11988 KB Output is correct
11 Correct 5 ms 11996 KB Output is correct
12 Correct 6 ms 11996 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 5 ms 11988 KB Output is correct
15 Correct 6 ms 11992 KB Output is correct
16 Correct 6 ms 11988 KB Output is correct
17 Correct 5 ms 11988 KB Output is correct
18 Correct 5 ms 12024 KB Output is correct
19 Correct 5 ms 11996 KB Output is correct
20 Correct 5 ms 11988 KB Output is correct
21 Correct 5 ms 12000 KB Output is correct
22 Correct 6 ms 12000 KB Output is correct
23 Correct 5 ms 12000 KB Output is correct
24 Correct 5 ms 12052 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11996 KB Output is correct
2 Correct 5 ms 11996 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 5 ms 11988 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Correct 5 ms 11992 KB Output is correct
7 Correct 5 ms 11988 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 5 ms 11988 KB Output is correct
10 Correct 5 ms 11988 KB Output is correct
11 Correct 5 ms 11996 KB Output is correct
12 Correct 6 ms 11996 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 5 ms 11988 KB Output is correct
15 Correct 6 ms 11992 KB Output is correct
16 Correct 6 ms 11988 KB Output is correct
17 Correct 5 ms 11988 KB Output is correct
18 Correct 5 ms 12024 KB Output is correct
19 Correct 5 ms 11996 KB Output is correct
20 Correct 5 ms 11988 KB Output is correct
21 Correct 5 ms 12000 KB Output is correct
22 Correct 6 ms 12000 KB Output is correct
23 Correct 5 ms 12000 KB Output is correct
24 Correct 5 ms 12052 KB Output is correct
25 Correct 6 ms 12244 KB Output is correct
26 Correct 6 ms 12264 KB Output is correct
27 Correct 6 ms 12244 KB Output is correct
28 Correct 6 ms 12244 KB Output is correct
29 Correct 6 ms 12244 KB Output is correct
30 Correct 6 ms 12244 KB Output is correct
31 Correct 7 ms 12324 KB Output is correct
32 Correct 6 ms 12244 KB Output is correct
33 Correct 7 ms 12272 KB Output is correct
34 Correct 6 ms 12244 KB Output is correct
35 Correct 6 ms 12244 KB Output is correct
36 Correct 6 ms 12136 KB Output is correct
37 Correct 6 ms 12396 KB Output is correct
38 Correct 7 ms 12240 KB Output is correct
39 Correct 6 ms 12164 KB Output is correct
40 Correct 6 ms 12140 KB Output is correct
41 Correct 6 ms 12372 KB Output is correct
42 Correct 9 ms 12372 KB Output is correct
43 Correct 6 ms 12396 KB Output is correct
44 Correct 6 ms 12392 KB Output is correct

Subtask #3
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11996 KB Output is correct
2 Correct 5 ms 11996 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 5 ms 11988 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Correct 5 ms 11992 KB Output is correct
7 Correct 5 ms 11988 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 5 ms 11988 KB Output is correct
10 Correct 5 ms 11988 KB Output is correct
11 Correct 5 ms 11996 KB Output is correct
12 Correct 6 ms 11996 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 5 ms 11988 KB Output is correct
15 Correct 6 ms 11992 KB Output is correct
16 Correct 6 ms 11988 KB Output is correct
17 Correct 5 ms 11988 KB Output is correct
18 Correct 5 ms 12024 KB Output is correct
19 Correct 5 ms 11996 KB Output is correct
20 Correct 5 ms 11988 KB Output is correct
21 Correct 5 ms 12000 KB Output is correct
22 Correct 6 ms 12000 KB Output is correct
23 Correct 5 ms 12000 KB Output is correct
24 Correct 5 ms 12052 KB Output is correct
25 Correct 6 ms 12244 KB Output is correct
26 Correct 6 ms 12264 KB Output is correct
27 Correct 6 ms 12244 KB Output is correct
28 Correct 6 ms 12244 KB Output is correct
29 Correct 6 ms 12244 KB Output is correct
30 Correct 6 ms 12244 KB Output is correct
31 Correct 7 ms 12324 KB Output is correct
32 Correct 6 ms 12244 KB Output is correct
33 Correct 7 ms 12272 KB Output is correct
34 Correct 6 ms 12244 KB Output is correct
35 Correct 6 ms 12244 KB Output is correct
36 Correct 6 ms 12136 KB Output is correct
37 Correct 6 ms 12396 KB Output is correct
38 Correct 7 ms 12240 KB Output is correct
39 Correct 6 ms 12164 KB Output is correct
40 Correct 6 ms 12140 KB Output is correct
41 Correct 6 ms 12372 KB Output is correct
42 Correct 9 ms 12372 KB Output is correct
43 Correct 6 ms 12396 KB Output is correct
44 Correct 6 ms 12392 KB Output is correct
45 Correct 65 ms 21820 KB Output is correct
46 Correct 62 ms 23160 KB Output is correct
47 Correct 63 ms 21068 KB Output is correct
48 Correct 64 ms 23120 KB Output is correct
49 Correct 61 ms 21160 KB Output is correct
50 Correct 63 ms 22768 KB Output is correct
51 Correct 62 ms 22692 KB Output is correct
52 Correct 49 ms 20380 KB Output is correct
53 Correct 56 ms 20696 KB Output is correct
54 Correct 68 ms 30060 KB Output is correct
55 Correct 65 ms 25164 KB Output is correct
56 Correct 67 ms 25264 KB Output is correct
57 Correct 45 ms 20308 KB Output is correct
58 Correct 45 ms 20376 KB Output is correct
59 Correct 53 ms 20528 KB Output is correct
60 Correct 55 ms 20512 KB Output is correct
61 Correct 58 ms 20428 KB Output is correct
62 Correct 52 ms 20428 KB Output is correct
63 Correct 53 ms 20416 KB Output is correct
64 Correct 57 ms 20284 KB Output is correct
65 Correct 90 ms 29892 KB Output is correct
66 Correct 91 ms 29892 KB Output is correct
67 Correct 75 ms 25196 KB Output is correct
68 Correct 74 ms 25360 KB Output is correct
69 Correct 71 ms 24728 KB Output is correct
70 Correct 73 ms 24760 KB Output is correct
71 Correct 69 ms 30152 KB Output is correct
72 Correct 70 ms 30136 KB Output is correct
73 Correct 66 ms 26996 KB Output is correct
74 Correct 69 ms 26980 KB Output is correct
75 Correct 50 ms 29648 KB Output is correct
76 Correct 47 ms 29764 KB Output is correct
77 Correct 51 ms 29764 KB Output is correct
78 Correct 62 ms 22872 KB Output is correct
79 Correct 60 ms 21952 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11996 KB Output is correct
2 Correct 5 ms 11996 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 5 ms 11988 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Correct 5 ms 11992 KB Output is correct
7 Correct 5 ms 11988 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 5 ms 11988 KB Output is correct
10 Correct 5 ms 11988 KB Output is correct
11 Correct 5 ms 11996 KB Output is correct
12 Correct 6 ms 11996 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 5 ms 11988 KB Output is correct
15 Correct 6 ms 11992 KB Output is correct
16 Correct 6 ms 11988 KB Output is correct
17 Correct 5 ms 11988 KB Output is correct
18 Correct 5 ms 12024 KB Output is correct
19 Correct 5 ms 11996 KB Output is correct
20 Correct 5 ms 11988 KB Output is correct
21 Correct 5 ms 12000 KB Output is correct
22 Correct 6 ms 12000 KB Output is correct
23 Correct 5 ms 12000 KB Output is correct
24 Correct 5 ms 12052 KB Output is correct
25 Correct 6 ms 12244 KB Output is correct
26 Correct 6 ms 12264 KB Output is correct
27 Correct 6 ms 12244 KB Output is correct
28 Correct 6 ms 12244 KB Output is correct
29 Correct 6 ms 12244 KB Output is correct
30 Correct 6 ms 12244 KB Output is correct
31 Correct 7 ms 12324 KB Output is correct
32 Correct 6 ms 12244 KB Output is correct
33 Correct 7 ms 12272 KB Output is correct
34 Correct 6 ms 12244 KB Output is correct
35 Correct 6 ms 12244 KB Output is correct
36 Correct 6 ms 12136 KB Output is correct
37 Correct 6 ms 12396 KB Output is correct
38 Correct 7 ms 12240 KB Output is correct
39 Correct 6 ms 12164 KB Output is correct
40 Correct 6 ms 12140 KB Output is correct
41 Correct 6 ms 12372 KB Output is correct
42 Correct 9 ms 12372 KB Output is correct
43 Correct 6 ms 12396 KB Output is correct
44 Correct 6 ms 12392 KB Output is correct
45 Correct 65 ms 21820 KB Output is correct
46 Correct 62 ms 23160 KB Output is correct
47 Correct 63 ms 21068 KB Output is correct
48 Correct 64 ms 23120 KB Output is correct
49 Correct 61 ms 21160 KB Output is correct
50 Correct 63 ms 22768 KB Output is correct
51 Correct 62 ms 22692 KB Output is correct
52 Correct 49 ms 20380 KB Output is correct
53 Correct 56 ms 20696 KB Output is correct
54 Correct 68 ms 30060 KB Output is correct
55 Correct 65 ms 25164 KB Output is correct
56 Correct 67 ms 25264 KB Output is correct
57 Correct 45 ms 20308 KB Output is correct
58 Correct 45 ms 20376 KB Output is correct
59 Correct 53 ms 20528 KB Output is correct
60 Correct 55 ms 20512 KB Output is correct
61 Correct 58 ms 20428 KB Output is correct
62 Correct 52 ms 20428 KB Output is correct
63 Correct 53 ms 20416 KB Output is correct
64 Correct 57 ms 20284 KB Output is correct
65 Correct 90 ms 29892 KB Output is correct
66 Correct 91 ms 29892 KB Output is correct
67 Correct 75 ms 25196 KB Output is correct
68 Correct 74 ms 25360 KB Output is correct
69 Correct 71 ms 24728 KB Output is correct
70 Correct 73 ms 24760 KB Output is correct
71 Correct 69 ms 30152 KB Output is correct
72 Correct 70 ms 30136 KB Output is correct
73 Correct 66 ms 26996 KB Output is correct
74 Correct 69 ms 26980 KB Output is correct
75 Correct 50 ms 29648 KB Output is correct
76 Correct 47 ms 29764 KB Output is correct
77 Correct 51 ms 29764 KB Output is correct
78 Correct 62 ms 22872 KB Output is correct
79 Correct 60 ms 21952 KB Output is correct
80 Correct 632 ms 104912 KB Output is correct
81 Correct 642 ms 103708 KB Output is correct
82 Correct 630 ms 100556 KB Output is correct
83 Correct 624 ms 103884 KB Output is correct
84 Correct 627 ms 104904 KB Output is correct
85 Correct 649 ms 100808 KB Output is correct
86 Correct 623 ms 103608 KB Output is correct
87 Correct 431 ms 96976 KB Output is correct
88 Correct 570 ms 101136 KB Output is correct
89 Correct 716 ms 195068 KB Output is correct
90 Correct 684 ms 146168 KB Output is correct
91 Correct 669 ms 146024 KB Output is correct
92 Correct 447 ms 97088 KB Output is correct
93 Correct 457 ms 97080 KB Output is correct
94 Correct 522 ms 98364 KB Output is correct
95 Correct 586 ms 98368 KB Output is correct
96 Correct 601 ms 98504 KB Output is correct
97 Correct 522 ms 98360 KB Output is correct
98 Correct 564 ms 97848 KB Output is correct
99 Correct 594 ms 98380 KB Output is correct
100 Correct 1494 ms 193064 KB Output is correct
101 Correct 1450 ms 193024 KB Output is correct
102 Correct 758 ms 146164 KB Output is correct
103 Correct 770 ms 146180 KB Output is correct
104 Correct 732 ms 141512 KB Output is correct
105 Correct 730 ms 141644 KB Output is correct
106 Correct 728 ms 195116 KB Output is correct
107 Correct 720 ms 195104 KB Output is correct
108 Correct 705 ms 163796 KB Output is correct
109 Correct 690 ms 163888 KB Output is correct
110 Correct 500 ms 190920 KB Output is correct
111 Correct 512 ms 190924 KB Output is correct
112 Correct 518 ms 190920 KB Output is correct
113 Correct 612 ms 99932 KB Output is correct
114 Correct 619 ms 103624 KB Output is correct