oj.uz

Submission #293036

# Submission time Handle Problem Language Result Execution time Memory
293036 2020-09-07T15:44:26 Z BThero Port Facility (JOI17_port_facility) C++17
100 / 100
 2839 ms 828196 KB 
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
 
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
const int MAXN = (int)1200005;
const int MOD = (int)1e9 + 7;
 
vector<pii> lt[MAXN * 4], rt[MAXN * 4];
int col[MAXN];
pii arr[MAXN];
int n;
 
bool cmp(pii a, pii b) {
  return a.se < b.se;
}
 
void addL(int v, int tl, int tr, int l, int r, int id) {
  if (tl == tr) {
    lt[v].pb(mp(r, id));
    return;
  }
  
  int mid = (tl + tr) >> 1;
  int c1 = (v << 1), c2 = (c1 | 1);
  
  if (l <= mid) {
    addL(c1, tl, mid, l, r, id);
  }
  else {
    addL(c2, mid + 1, tr, l, r, id);
  }
}

void addR(int v, int tl, int tr, int l, int r, int id) {
  if (tl == tr) {
    rt[v].pb(mp(l, id));
    return;
  }
  
  int mid = (tl + tr) >> 1;
  int c1 = (v << 1), c2 = (c1 | 1);
  
  if (r <= mid) {
    addR(c1, tl, mid, l, r, id);
  }
  else {
    addR(c2, mid + 1, tr, l, r, id);
  }
}

void prep(int v, int tl, int tr) {
  if (tl != tr) {
    int mid = (tl + tr) >> 1;
    int c1 = (v << 1), c2 = (c1 | 1);
    prep(c1, tl, mid);
    prep(c2, mid + 1, tr);
    lt[v].resize(lt[c1].size() + lt[c2].size());
    rt[v].resize(rt[c1].size() + rt[c2].size());
    merge(all(lt[c1]), all(lt[c2]), lt[v].begin());
    merge(all(rt[c1]), all(rt[c2]), rt[v].begin());
  }
}

void prep2(int v, int tl, int tr) {
  reverse(all(rt[v]));
  
  if (tl != tr) {
    int mid = (tl + tr) >> 1;
    int c1 = (v << 1), c2 = (c1 | 1);
    prep2(c1, tl, mid);
    prep2(c2, mid + 1, tr);
  }
}

void go(int v, int tl, int tr, int l, int r, int limL, int limR, vector<int> &e) {
  if (l > r || tl > r || tr < l) {
    return;
  }
  
  if (l <= tl && tr <= r) {
    while (!lt[v].empty() && lt[v].back().fi >= limL) {
      e.pb(lt[v].back().se);
      lt[v].pop_back();
    }
    
    while (!rt[v].empty() && rt[v].back().fi <= limR) {
      e.pb(rt[v].back().se);
      rt[v].pop_back();
    }
    
    return;
  }
  
  int mid = (tl + tr) >> 1;
  int c1 = (v << 1), c2 = (c1 | 1);
  go(c1, tl, mid, l, r, limL, limR, e);
  go(c2, mid + 1, tr, l, r, limL, limR, e);
}
 
void dfs(int v) {
  vector<int> e;
  go(1, 1, 2 * n, arr[v].fi + 1, arr[v].se - 1, arr[v].se + 1, arr[v].fi - 1, e);
  
  for (int to : e) {
    if (col[to] == -1) {
      col[to] = 1 - col[v];
      dfs(to);
    }
    else if (col[to] == col[v]) {
      printf("0\n");
      exit(0);
    }
  }
}
 
void solve() {
  scanf("%d", &n);
  
  for (int i = 1; i <= n; ++i) {
    scanf("%d %d", &arr[i].fi, &arr[i].se);
  }
  
  sort(arr + 1, arr + n + 1, cmp);
  
  for (int i = 1; i <= n; ++i) {
    addL(1, 1, 2 * n, arr[i].fi, arr[i].se, i);
    addR(1, 1, 2 * n, arr[i].fi, arr[i].se, i);
  }
  
  prep(1, 1, 2 * n);
  prep2(1, 1, 2 * n);
  fill(col + 1, col + n + 1, -1);
  int ans = 1;
  
  for (int i = 1; i <= n; ++i) {
    if (col[i] == -1) {
      col[i] = 0;
      dfs(i);
      ans = (ans * 2) % MOD;
    }
  }
  
  printf("%d\n", ans);
}
 
int main() {
  int tt = 1;
  
  while (tt--) {
    solve();
  }
 
  return 0;
}

Compilation message

port_facility.cpp: In function 'void solve()':
port_facility.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  129 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
port_facility.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |     scanf("%d %d", &arr[i].fi, &arr[i].se);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 225784 KB Output is correct
2 Correct 160 ms 225784 KB Output is correct
3 Correct 158 ms 225784 KB Output is correct
4 Correct 156 ms 225784 KB Output is correct
5 Correct 153 ms 225784 KB Output is correct
6 Correct 154 ms 225784 KB Output is correct
7 Correct 152 ms 225784 KB Output is correct
8 Correct 153 ms 225784 KB Output is correct
9 Correct 156 ms 225784 KB Output is correct
10 Correct 155 ms 225812 KB Output is correct
11 Correct 154 ms 225788 KB Output is correct
12 Correct 168 ms 225784 KB Output is correct
13 Correct 173 ms 225792 KB Output is correct
14 Correct 162 ms 225740 KB Output is correct
15 Correct 152 ms 225784 KB Output is correct
16 Correct 164 ms 225924 KB Output is correct
17 Correct 173 ms 225784 KB Output is correct
18 Correct 156 ms 225784 KB Output is correct
19 Correct 166 ms 225784 KB Output is correct
20 Correct 174 ms 225740 KB Output is correct
21 Correct 165 ms 225784 KB Output is correct
22 Correct 156 ms 225784 KB Output is correct
23 Correct 167 ms 225784 KB Output is correct
24 Correct 154 ms 225788 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 225784 KB Output is correct
2 Correct 160 ms 225784 KB Output is correct
3 Correct 158 ms 225784 KB Output is correct
4 Correct 156 ms 225784 KB Output is correct
5 Correct 153 ms 225784 KB Output is correct
6 Correct 154 ms 225784 KB Output is correct
7 Correct 152 ms 225784 KB Output is correct
8 Correct 153 ms 225784 KB Output is correct
9 Correct 156 ms 225784 KB Output is correct
10 Correct 155 ms 225812 KB Output is correct
11 Correct 154 ms 225788 KB Output is correct
12 Correct 168 ms 225784 KB Output is correct
13 Correct 173 ms 225792 KB Output is correct
14 Correct 162 ms 225740 KB Output is correct
15 Correct 152 ms 225784 KB Output is correct
16 Correct 164 ms 225924 KB Output is correct
17 Correct 173 ms 225784 KB Output is correct
18 Correct 156 ms 225784 KB Output is correct
19 Correct 166 ms 225784 KB Output is correct
20 Correct 174 ms 225740 KB Output is correct
21 Correct 165 ms 225784 KB Output is correct
22 Correct 156 ms 225784 KB Output is correct
23 Correct 167 ms 225784 KB Output is correct
24 Correct 154 ms 225788 KB Output is correct
25 Correct 167 ms 226440 KB Output is correct
26 Correct 159 ms 226552 KB Output is correct
27 Correct 159 ms 226424 KB Output is correct
28 Correct 156 ms 226424 KB Output is correct
29 Correct 160 ms 226552 KB Output is correct
30 Correct 158 ms 226424 KB Output is correct
31 Correct 156 ms 226424 KB Output is correct
32 Correct 156 ms 226424 KB Output is correct
33 Correct 157 ms 226424 KB Output is correct
34 Correct 157 ms 226424 KB Output is correct
35 Correct 156 ms 226424 KB Output is correct
36 Correct 161 ms 226424 KB Output is correct
37 Correct 163 ms 226336 KB Output is correct
38 Correct 157 ms 226424 KB Output is correct
39 Correct 160 ms 226424 KB Output is correct
40 Correct 155 ms 226424 KB Output is correct
41 Correct 154 ms 226328 KB Output is correct
42 Correct 159 ms 226424 KB Output is correct
43 Correct 161 ms 226856 KB Output is correct
44 Correct 156 ms 226680 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 225784 KB Output is correct
2 Correct 160 ms 225784 KB Output is correct
3 Correct 158 ms 225784 KB Output is correct
4 Correct 156 ms 225784 KB Output is correct
5 Correct 153 ms 225784 KB Output is correct
6 Correct 154 ms 225784 KB Output is correct
7 Correct 152 ms 225784 KB Output is correct
8 Correct 153 ms 225784 KB Output is correct
9 Correct 156 ms 225784 KB Output is correct
10 Correct 155 ms 225812 KB Output is correct
11 Correct 154 ms 225788 KB Output is correct
12 Correct 168 ms 225784 KB Output is correct
13 Correct 173 ms 225792 KB Output is correct
14 Correct 162 ms 225740 KB Output is correct
15 Correct 152 ms 225784 KB Output is correct
16 Correct 164 ms 225924 KB Output is correct
17 Correct 173 ms 225784 KB Output is correct
18 Correct 156 ms 225784 KB Output is correct
19 Correct 166 ms 225784 KB Output is correct
20 Correct 174 ms 225740 KB Output is correct
21 Correct 165 ms 225784 KB Output is correct
22 Correct 156 ms 225784 KB Output is correct
23 Correct 167 ms 225784 KB Output is correct
24 Correct 154 ms 225788 KB Output is correct
25 Correct 167 ms 226440 KB Output is correct
26 Correct 159 ms 226552 KB Output is correct
27 Correct 159 ms 226424 KB Output is correct
28 Correct 156 ms 226424 KB Output is correct
29 Correct 160 ms 226552 KB Output is correct
30 Correct 158 ms 226424 KB Output is correct
31 Correct 156 ms 226424 KB Output is correct
32 Correct 156 ms 226424 KB Output is correct
33 Correct 157 ms 226424 KB Output is correct
34 Correct 157 ms 226424 KB Output is correct
35 Correct 156 ms 226424 KB Output is correct
36 Correct 161 ms 226424 KB Output is correct
37 Correct 163 ms 226336 KB Output is correct
38 Correct 157 ms 226424 KB Output is correct
39 Correct 160 ms 226424 KB Output is correct
40 Correct 155 ms 226424 KB Output is correct
41 Correct 154 ms 226328 KB Output is correct
42 Correct 159 ms 226424 KB Output is correct
43 Correct 161 ms 226856 KB Output is correct
44 Correct 156 ms 226680 KB Output is correct
45 Correct 400 ms 267340 KB Output is correct
46 Correct 412 ms 267768 KB Output is correct
47 Correct 441 ms 267200 KB Output is correct
48 Correct 439 ms 267768 KB Output is correct
49 Correct 456 ms 267200 KB Output is correct
50 Correct 366 ms 267256 KB Output is correct
51 Correct 387 ms 267384 KB Output is correct
52 Correct 348 ms 269184 KB Output is correct
53 Correct 369 ms 264544 KB Output is correct
54 Correct 320 ms 265172 KB Output is correct
55 Correct 300 ms 265204 KB Output is correct
56 Correct 302 ms 264824 KB Output is correct
57 Correct 369 ms 268280 KB Output is correct
58 Correct 364 ms 268348 KB Output is correct
59 Correct 368 ms 267900 KB Output is correct
60 Correct 410 ms 267184 KB Output is correct
61 Correct 428 ms 267000 KB Output is correct
62 Correct 433 ms 268272 KB Output is correct
63 Correct 352 ms 267384 KB Output is correct
64 Correct 352 ms 267032 KB Output is correct
65 Correct 365 ms 267932 KB Output is correct
66 Correct 375 ms 267968 KB Output is correct
67 Correct 465 ms 266832 KB Output is correct
68 Correct 425 ms 266980 KB Output is correct
69 Correct 389 ms 266784 KB Output is correct
70 Correct 407 ms 266768 KB Output is correct
71 Correct 349 ms 265308 KB Output is correct
72 Correct 352 ms 265204 KB Output is correct
73 Correct 343 ms 265324 KB Output is correct
74 Correct 340 ms 265204 KB Output is correct
75 Correct 398 ms 280312 KB Output is correct
76 Correct 383 ms 280184 KB Output is correct
77 Correct 406 ms 280316 KB Output is correct
78 Correct 420 ms 267648 KB Output is correct
79 Correct 404 ms 267256 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 225784 KB Output is correct
2 Correct 160 ms 225784 KB Output is correct
3 Correct 158 ms 225784 KB Output is correct
4 Correct 156 ms 225784 KB Output is correct
5 Correct 153 ms 225784 KB Output is correct
6 Correct 154 ms 225784 KB Output is correct
7 Correct 152 ms 225784 KB Output is correct
8 Correct 153 ms 225784 KB Output is correct
9 Correct 156 ms 225784 KB Output is correct
10 Correct 155 ms 225812 KB Output is correct
11 Correct 154 ms 225788 KB Output is correct
12 Correct 168 ms 225784 KB Output is correct
13 Correct 173 ms 225792 KB Output is correct
14 Correct 162 ms 225740 KB Output is correct
15 Correct 152 ms 225784 KB Output is correct
16 Correct 164 ms 225924 KB Output is correct
17 Correct 173 ms 225784 KB Output is correct
18 Correct 156 ms 225784 KB Output is correct
19 Correct 166 ms 225784 KB Output is correct
20 Correct 174 ms 225740 KB Output is correct
21 Correct 165 ms 225784 KB Output is correct
22 Correct 156 ms 225784 KB Output is correct
23 Correct 167 ms 225784 KB Output is correct
24 Correct 154 ms 225788 KB Output is correct
25 Correct 167 ms 226440 KB Output is correct
26 Correct 159 ms 226552 KB Output is correct
27 Correct 159 ms 226424 KB Output is correct
28 Correct 156 ms 226424 KB Output is correct
29 Correct 160 ms 226552 KB Output is correct
30 Correct 158 ms 226424 KB Output is correct
31 Correct 156 ms 226424 KB Output is correct
32 Correct 156 ms 226424 KB Output is correct
33 Correct 157 ms 226424 KB Output is correct
34 Correct 157 ms 226424 KB Output is correct
35 Correct 156 ms 226424 KB Output is correct
36 Correct 161 ms 226424 KB Output is correct
37 Correct 163 ms 226336 KB Output is correct
38 Correct 157 ms 226424 KB Output is correct
39 Correct 160 ms 226424 KB Output is correct
40 Correct 155 ms 226424 KB Output is correct
41 Correct 154 ms 226328 KB Output is correct
42 Correct 159 ms 226424 KB Output is correct
43 Correct 161 ms 226856 KB Output is correct
44 Correct 156 ms 226680 KB Output is correct
45 Correct 400 ms 267340 KB Output is correct
46 Correct 412 ms 267768 KB Output is correct
47 Correct 441 ms 267200 KB Output is correct
48 Correct 439 ms 267768 KB Output is correct
49 Correct 456 ms 267200 KB Output is correct
50 Correct 366 ms 267256 KB Output is correct
51 Correct 387 ms 267384 KB Output is correct
52 Correct 348 ms 269184 KB Output is correct
53 Correct 369 ms 264544 KB Output is correct
54 Correct 320 ms 265172 KB Output is correct
55 Correct 300 ms 265204 KB Output is correct
56 Correct 302 ms 264824 KB Output is correct
57 Correct 369 ms 268280 KB Output is correct
58 Correct 364 ms 268348 KB Output is correct
59 Correct 368 ms 267900 KB Output is correct
60 Correct 410 ms 267184 KB Output is correct
61 Correct 428 ms 267000 KB Output is correct
62 Correct 433 ms 268272 KB Output is correct
63 Correct 352 ms 267384 KB Output is correct
64 Correct 352 ms 267032 KB Output is correct
65 Correct 365 ms 267932 KB Output is correct
66 Correct 375 ms 267968 KB Output is correct
67 Correct 465 ms 266832 KB Output is correct
68 Correct 425 ms 266980 KB Output is correct
69 Correct 389 ms 266784 KB Output is correct
70 Correct 407 ms 266768 KB Output is correct
71 Correct 349 ms 265308 KB Output is correct
72 Correct 352 ms 265204 KB Output is correct
73 Correct 343 ms 265324 KB Output is correct
74 Correct 340 ms 265204 KB Output is correct
75 Correct 398 ms 280312 KB Output is correct
76 Correct 383 ms 280184 KB Output is correct
77 Correct 406 ms 280316 KB Output is correct
78 Correct 420 ms 267648 KB Output is correct
79 Correct 404 ms 267256 KB Output is correct
80 Correct 2808 ms 681716 KB Output is correct
81 Correct 2836 ms 681284 KB Output is correct
82 Correct 2825 ms 681580 KB Output is correct
83 Correct 2734 ms 681044 KB Output is correct
84 Correct 2761 ms 681308 KB Output is correct
85 Correct 2358 ms 680800 KB Output is correct
86 Correct 2484 ms 680812 KB Output is correct
87 Correct 2067 ms 704040 KB Output is correct
88 Correct 2061 ms 657060 KB Output is correct
89 Correct 1639 ms 661272 KB Output is correct
90 Correct 1690 ms 664104 KB Output is correct
91 Correct 1670 ms 659248 KB Output is correct
92 Correct 2318 ms 689580 KB Output is correct
93 Correct 2202 ms 689480 KB Output is correct
94 Correct 2497 ms 684464 KB Output is correct
95 Correct 2665 ms 680084 KB Output is correct
96 Correct 2725 ms 678904 KB Output is correct
97 Correct 2181 ms 685680 KB Output is correct
98 Correct 2349 ms 681200 KB Output is correct
99 Correct 2252 ms 681452 KB Output is correct
100 Correct 2585 ms 678644 KB Output is correct
101 Correct 2648 ms 696336 KB Output is correct
102 Correct 2707 ms 692684 KB Output is correct
103 Correct 2745 ms 692660 KB Output is correct
104 Correct 2679 ms 692704 KB Output is correct
105 Correct 2736 ms 692728 KB Output is correct
106 Correct 2214 ms 677608 KB Output is correct
107 Correct 2219 ms 676712 KB Output is correct
108 Correct 2283 ms 677692 KB Output is correct
109 Correct 2119 ms 677720 KB Output is correct
110 Correct 2689 ms 828052 KB Output is correct
111 Correct 2621 ms 828196 KB Output is correct
112 Correct 2516 ms 828152 KB Output is correct
113 Correct 2838 ms 694008 KB Output is correct
114 Correct 2839 ms 694416 KB Output is correct