oj.uz

답안 #972834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972834 2024-05-01T08:47:48 Z abczz Port Facility (JOI17_port_facility) C++14
100 / 100
 2247 ms 975100 KB 
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <map>
#define ll long long

using namespace std;

bool B[2000000];
vector <ll> V;
vector <array<ll, 2> > R, Q;
ll A[2000000], L[2000000], M = 1e9 + 7;
struct SegTree{
  vector <ll> st[8000000];
  vector <ll> st2[8000000];
  void build(ll id, ll l, ll r) {
    if (l == r) {
      if (A[l] != -1) st[id].push_back(A[l]);
      else st2[id].push_back(L[l]);
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    int i = 0, j = 0;
    while (i < st[id*2].size() && j < st[id*2+1].size()) {
      if (st[id*2][i] < st[id*2+1][j]) st[id].push_back(st[id*2][i++]);
      else st[id].push_back(st[id*2+1][j++]);
    }
    while (i < st[id*2].size()) st[id].push_back(st[id*2][i++]);
    while (j < st[id*2+1].size()) st[id].push_back(st[id*2+1][j++]);
    i = 0, j = 0;
    while (i < st2[id*2].size() && j < st2[id*2+1].size()) {
      if (st2[id*2][i] > st2[id*2+1][j]) st2[id].push_back(st2[id*2][i++]);
      else st2[id].push_back(st2[id*2+1][j++]);
    }
    while (i < st2[id*2].size()) st2[id].push_back(st2[id*2][i++]);
    while (j < st2[id*2+1].size()) st2[id].push_back(st2[id*2+1][j++]);
  }
  void query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      while (!st[id].empty()) {
        auto u = st[id].back();
        if (B[u] || qr < u) {
          if (!B[u]) {
            R.push_back({L[u], u});
            B[L[u]] = B[u] = 1;
          }
          st[id].pop_back();
        }
        else break;
      }
      while (!st2[id].empty()) {
        auto u = st2[id].back();
        if (B[u] || u < ql) {
          if (!B[u]) {
            R.push_back({u, A[u]});
            B[u] = B[A[u]] = 1;
          }
          st2[id].pop_back();
        }
        else break;
      }
      return;
    }
    ll mid = (l+r)/2;
    query(id*2, l, mid, ql, qr);
    query(id*2+1, mid+1, r, ql, qr);
  }
} ST;
ll n, a, b, f = 1;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n;
  for (int i=0; i<2*n; ++i) A[i] = L[i] = -1;
  for (int i=0; i<n; ++i) {
    cin >> a >> b;
    --a, --b;
    L[b] = a;
    A[a] = b;
  }
  ST.build(1, 0, 2*n-1);
  for (int i=0; i<2*n; ++i) {
    if (!B[i]) {
      f *= 2;
      f %= M;
      B[i] = B[A[i]] = 1;
      R.clear();
      Q.clear();
      Q.push_back({i, A[i]});
      while (true) {
        for (auto [l, r] : Q) {
          ST.query(1, 0, 2*n-1, l, r);
        }
        Q.clear();
        V.clear();
        if (R.empty()) break;
        sort(R.begin(), R.end());
        for (auto [x, y] : R) {
          while (!V.empty() && V.back() < x) {
            V.pop_back();
          }
          if (!V.empty() && V.back() < y) {
            cout << "0\n";
            return 0;
          }
          V.push_back(y);
        }
        swap(R, Q);
      }
    }
  }
  cout << f << '\n';
}

Compilation message

port_facility.cpp: In member function 'void SegTree::build(long long int, long long int, long long int)':
port_facility.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while (i < st[id*2].size() && j < st[id*2+1].size()) {
      |            ~~^~~~~~~~~~~~~~~~~
port_facility.cpp:27:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while (i < st[id*2].size() && j < st[id*2+1].size()) {
      |                                   ~~^~~~~~~~~~~~~~~~~~~
port_facility.cpp:31:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     while (i < st[id*2].size()) st[id].push_back(st[id*2][i++]);
      |            ~~^~~~~~~~~~~~~~~~~
port_facility.cpp:32:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while (j < st[id*2+1].size()) st[id].push_back(st[id*2+1][j++]);
      |            ~~^~~~~~~~~~~~~~~~~~~
port_facility.cpp:34:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while (i < st2[id*2].size() && j < st2[id*2+1].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~
port_facility.cpp:34:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while (i < st2[id*2].size() && j < st2[id*2+1].size()) {
      |                                    ~~^~~~~~~~~~~~~~~~~~~~
port_facility.cpp:38:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     while (i < st2[id*2].size()) st2[id].push_back(st2[id*2][i++]);
      |            ~~^~~~~~~~~~~~~~~~~~
port_facility.cpp:39:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while (j < st2[id*2+1].size()) st2[id].push_back(st2[id*2+1][j++]);
      |            ~~^~~~~~~~~~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:95:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |         for (auto [l, r] : Q) {
      |                   ^
port_facility.cpp:102:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         for (auto [x, y] : R) {
      |                   ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 378076 KB Output is correct
2 Correct 154 ms 378220 KB Output is correct
3 Correct 166 ms 378376 KB Output is correct
4 Correct 152 ms 378164 KB Output is correct
5 Correct 151 ms 378112 KB Output is correct
6 Correct 153 ms 378184 KB Output is correct
7 Correct 157 ms 378188 KB Output is correct
8 Correct 156 ms 378052 KB Output is correct
9 Correct 152 ms 378196 KB Output is correct
10 Correct 160 ms 378188 KB Output is correct
11 Correct 155 ms 378192 KB Output is correct
12 Correct 152 ms 378140 KB Output is correct
13 Correct 153 ms 378032 KB Output is correct
14 Correct 152 ms 378196 KB Output is correct
15 Correct 151 ms 378160 KB Output is correct
16 Correct 156 ms 378152 KB Output is correct
17 Correct 156 ms 378172 KB Output is correct
18 Correct 162 ms 378200 KB Output is correct
19 Correct 150 ms 378192 KB Output is correct
20 Correct 176 ms 378308 KB Output is correct
21 Correct 152 ms 378080 KB Output is correct
22 Correct 152 ms 378064 KB Output is correct
23 Correct 158 ms 378452 KB Output is correct
24 Correct 153 ms 378196 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 378076 KB Output is correct
2 Correct 154 ms 378220 KB Output is correct
3 Correct 166 ms 378376 KB Output is correct
4 Correct 152 ms 378164 KB Output is correct
5 Correct 151 ms 378112 KB Output is correct
6 Correct 153 ms 378184 KB Output is correct
7 Correct 157 ms 378188 KB Output is correct
8 Correct 156 ms 378052 KB Output is correct
9 Correct 152 ms 378196 KB Output is correct
10 Correct 160 ms 378188 KB Output is correct
11 Correct 155 ms 378192 KB Output is correct
12 Correct 152 ms 378140 KB Output is correct
13 Correct 153 ms 378032 KB Output is correct
14 Correct 152 ms 378196 KB Output is correct
15 Correct 151 ms 378160 KB Output is correct
16 Correct 156 ms 378152 KB Output is correct
17 Correct 156 ms 378172 KB Output is correct
18 Correct 162 ms 378200 KB Output is correct
19 Correct 150 ms 378192 KB Output is correct
20 Correct 176 ms 378308 KB Output is correct
21 Correct 152 ms 378080 KB Output is correct
22 Correct 152 ms 378064 KB Output is correct
23 Correct 158 ms 378452 KB Output is correct
24 Correct 153 ms 378196 KB Output is correct
25 Correct 160 ms 378864 KB Output is correct
26 Correct 153 ms 379024 KB Output is correct
27 Correct 154 ms 378964 KB Output is correct
28 Correct 202 ms 378972 KB Output is correct
29 Correct 160 ms 378816 KB Output is correct
30 Correct 197 ms 379228 KB Output is correct
31 Correct 156 ms 379120 KB Output is correct
32 Correct 160 ms 378960 KB Output is correct
33 Correct 159 ms 379112 KB Output is correct
34 Correct 156 ms 379012 KB Output is correct
35 Correct 156 ms 378888 KB Output is correct
36 Correct 156 ms 378796 KB Output is correct
37 Correct 158 ms 378960 KB Output is correct
38 Correct 155 ms 378844 KB Output is correct
39 Correct 153 ms 378964 KB Output is correct
40 Correct 163 ms 378964 KB Output is correct
41 Correct 160 ms 378796 KB Output is correct
42 Correct 157 ms 378712 KB Output is correct
43 Correct 154 ms 378912 KB Output is correct
44 Correct 160 ms 378948 KB Output is correct

Subtask #3
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 378076 KB Output is correct
2 Correct 154 ms 378220 KB Output is correct
3 Correct 166 ms 378376 KB Output is correct
4 Correct 152 ms 378164 KB Output is correct
5 Correct 151 ms 378112 KB Output is correct
6 Correct 153 ms 378184 KB Output is correct
7 Correct 157 ms 378188 KB Output is correct
8 Correct 156 ms 378052 KB Output is correct
9 Correct 152 ms 378196 KB Output is correct
10 Correct 160 ms 378188 KB Output is correct
11 Correct 155 ms 378192 KB Output is correct
12 Correct 152 ms 378140 KB Output is correct
13 Correct 153 ms 378032 KB Output is correct
14 Correct 152 ms 378196 KB Output is correct
15 Correct 151 ms 378160 KB Output is correct
16 Correct 156 ms 378152 KB Output is correct
17 Correct 156 ms 378172 KB Output is correct
18 Correct 162 ms 378200 KB Output is correct
19 Correct 150 ms 378192 KB Output is correct
20 Correct 176 ms 378308 KB Output is correct
21 Correct 152 ms 378080 KB Output is correct
22 Correct 152 ms 378064 KB Output is correct
23 Correct 158 ms 378452 KB Output is correct
24 Correct 153 ms 378196 KB Output is correct
25 Correct 160 ms 378864 KB Output is correct
26 Correct 153 ms 379024 KB Output is correct
27 Correct 154 ms 378964 KB Output is correct
28 Correct 202 ms 378972 KB Output is correct
29 Correct 160 ms 378816 KB Output is correct
30 Correct 197 ms 379228 KB Output is correct
31 Correct 156 ms 379120 KB Output is correct
32 Correct 160 ms 378960 KB Output is correct
33 Correct 159 ms 379112 KB Output is correct
34 Correct 156 ms 379012 KB Output is correct
35 Correct 156 ms 378888 KB Output is correct
36 Correct 156 ms 378796 KB Output is correct
37 Correct 158 ms 378960 KB Output is correct
38 Correct 155 ms 378844 KB Output is correct
39 Correct 153 ms 378964 KB Output is correct
40 Correct 163 ms 378964 KB Output is correct
41 Correct 160 ms 378796 KB Output is correct
42 Correct 157 ms 378712 KB Output is correct
43 Correct 154 ms 378912 KB Output is correct
44 Correct 160 ms 378948 KB Output is correct
45 Correct 322 ms 430432 KB Output is correct
46 Correct 312 ms 430384 KB Output is correct
47 Correct 307 ms 430284 KB Output is correct
48 Correct 327 ms 430664 KB Output is correct
49 Correct 325 ms 430408 KB Output is correct
50 Correct 280 ms 430404 KB Output is correct
51 Correct 292 ms 430152 KB Output is correct
52 Correct 296 ms 430740 KB Output is correct
53 Correct 268 ms 426080 KB Output is correct
54 Correct 233 ms 427972 KB Output is correct
55 Correct 231 ms 426736 KB Output is correct
56 Correct 234 ms 426904 KB Output is correct
57 Correct 297 ms 429332 KB Output is correct
58 Correct 303 ms 429476 KB Output is correct
59 Correct 309 ms 432964 KB Output is correct
60 Correct 329 ms 432260 KB Output is correct
61 Correct 314 ms 431172 KB Output is correct
62 Correct 279 ms 433296 KB Output is correct
63 Correct 289 ms 431940 KB Output is correct
64 Correct 274 ms 431212 KB Output is correct
65 Correct 278 ms 428900 KB Output is correct
66 Correct 284 ms 428488 KB Output is correct
67 Correct 304 ms 429956 KB Output is correct
68 Correct 354 ms 429748 KB Output is correct
69 Correct 307 ms 432228 KB Output is correct
70 Correct 292 ms 432020 KB Output is correct
71 Correct 263 ms 428164 KB Output is correct
72 Correct 268 ms 428236 KB Output is correct
73 Correct 266 ms 428736 KB Output is correct
74 Correct 272 ms 428544 KB Output is correct
75 Correct 297 ms 430652 KB Output is correct
76 Correct 304 ms 430704 KB Output is correct
77 Correct 303 ms 430720 KB Output is correct
78 Correct 323 ms 430152 KB Output is correct
79 Correct 319 ms 430152 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 378076 KB Output is correct
2 Correct 154 ms 378220 KB Output is correct
3 Correct 166 ms 378376 KB Output is correct
4 Correct 152 ms 378164 KB Output is correct
5 Correct 151 ms 378112 KB Output is correct
6 Correct 153 ms 378184 KB Output is correct
7 Correct 157 ms 378188 KB Output is correct
8 Correct 156 ms 378052 KB Output is correct
9 Correct 152 ms 378196 KB Output is correct
10 Correct 160 ms 378188 KB Output is correct
11 Correct 155 ms 378192 KB Output is correct
12 Correct 152 ms 378140 KB Output is correct
13 Correct 153 ms 378032 KB Output is correct
14 Correct 152 ms 378196 KB Output is correct
15 Correct 151 ms 378160 KB Output is correct
16 Correct 156 ms 378152 KB Output is correct
17 Correct 156 ms 378172 KB Output is correct
18 Correct 162 ms 378200 KB Output is correct
19 Correct 150 ms 378192 KB Output is correct
20 Correct 176 ms 378308 KB Output is correct
21 Correct 152 ms 378080 KB Output is correct
22 Correct 152 ms 378064 KB Output is correct
23 Correct 158 ms 378452 KB Output is correct
24 Correct 153 ms 378196 KB Output is correct
25 Correct 160 ms 378864 KB Output is correct
26 Correct 153 ms 379024 KB Output is correct
27 Correct 154 ms 378964 KB Output is correct
28 Correct 202 ms 378972 KB Output is correct
29 Correct 160 ms 378816 KB Output is correct
30 Correct 197 ms 379228 KB Output is correct
31 Correct 156 ms 379120 KB Output is correct
32 Correct 160 ms 378960 KB Output is correct
33 Correct 159 ms 379112 KB Output is correct
34 Correct 156 ms 379012 KB Output is correct
35 Correct 156 ms 378888 KB Output is correct
36 Correct 156 ms 378796 KB Output is correct
37 Correct 158 ms 378960 KB Output is correct
38 Correct 155 ms 378844 KB Output is correct
39 Correct 153 ms 378964 KB Output is correct
40 Correct 163 ms 378964 KB Output is correct
41 Correct 160 ms 378796 KB Output is correct
42 Correct 157 ms 378712 KB Output is correct
43 Correct 154 ms 378912 KB Output is correct
44 Correct 160 ms 378948 KB Output is correct
45 Correct 322 ms 430432 KB Output is correct
46 Correct 312 ms 430384 KB Output is correct
47 Correct 307 ms 430284 KB Output is correct
48 Correct 327 ms 430664 KB Output is correct
49 Correct 325 ms 430408 KB Output is correct
50 Correct 280 ms 430404 KB Output is correct
51 Correct 292 ms 430152 KB Output is correct
52 Correct 296 ms 430740 KB Output is correct
53 Correct 268 ms 426080 KB Output is correct
54 Correct 233 ms 427972 KB Output is correct
55 Correct 231 ms 426736 KB Output is correct
56 Correct 234 ms 426904 KB Output is correct
57 Correct 297 ms 429332 KB Output is correct
58 Correct 303 ms 429476 KB Output is correct
59 Correct 309 ms 432964 KB Output is correct
60 Correct 329 ms 432260 KB Output is correct
61 Correct 314 ms 431172 KB Output is correct
62 Correct 279 ms 433296 KB Output is correct
63 Correct 289 ms 431940 KB Output is correct
64 Correct 274 ms 431212 KB Output is correct
65 Correct 278 ms 428900 KB Output is correct
66 Correct 284 ms 428488 KB Output is correct
67 Correct 304 ms 429956 KB Output is correct
68 Correct 354 ms 429748 KB Output is correct
69 Correct 307 ms 432228 KB Output is correct
70 Correct 292 ms 432020 KB Output is correct
71 Correct 263 ms 428164 KB Output is correct
72 Correct 268 ms 428236 KB Output is correct
73 Correct 266 ms 428736 KB Output is correct
74 Correct 272 ms 428544 KB Output is correct
75 Correct 297 ms 430652 KB Output is correct
76 Correct 304 ms 430704 KB Output is correct
77 Correct 303 ms 430720 KB Output is correct
78 Correct 323 ms 430152 KB Output is correct
79 Correct 319 ms 430152 KB Output is correct
80 Correct 2098 ms 938228 KB Output is correct
81 Correct 2051 ms 938680 KB Output is correct
82 Correct 2032 ms 938232 KB Output is correct
83 Correct 2033 ms 938344 KB Output is correct
84 Correct 1994 ms 938372 KB Output is correct
85 Correct 1780 ms 937768 KB Output is correct
86 Correct 1819 ms 938524 KB Output is correct
87 Correct 1789 ms 911336 KB Output is correct
88 Correct 1464 ms 864344 KB Output is correct
89 Correct 1148 ms 880636 KB Output is correct
90 Correct 1097 ms 871832 KB Output is correct
91 Correct 1152 ms 871572 KB Output is correct
92 Correct 1726 ms 896188 KB Output is correct
93 Correct 1815 ms 896408 KB Output is correct
94 Correct 2247 ms 975100 KB Output is correct
95 Correct 2036 ms 962796 KB Output is correct
96 Correct 1959 ms 949456 KB Output is correct
97 Correct 1752 ms 974692 KB Output is correct
98 Correct 1820 ms 962360 KB Output is correct
99 Correct 1672 ms 949752 KB Output is correct
100 Correct 1643 ms 904428 KB Output is correct
101 Correct 1650 ms 904672 KB Output is correct
102 Correct 1957 ms 917232 KB Output is correct
103 Correct 1893 ms 917048 KB Output is correct
104 Correct 1915 ms 945052 KB Output is correct
105 Correct 1931 ms 944792 KB Output is correct
106 Correct 1487 ms 885860 KB Output is correct
107 Correct 1428 ms 885944 KB Output is correct
108 Correct 1480 ms 887300 KB Output is correct
109 Correct 1499 ms 887272 KB Output is correct
110 Correct 1749 ms 911156 KB Output is correct
111 Correct 1809 ms 911224 KB Output is correct
112 Correct 1865 ms 911268 KB Output is correct
113 Correct 1992 ms 938556 KB Output is correct
114 Correct 2001 ms 938564 KB Output is correct