oj.uz

답안 #866737

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
866737 2023-10-27T01:34:37 Z mgl_diamond Port Facility (JOI17_port_facility) C++17
0 / 100
 1 ms 2804 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int MOD = 1e9+7;
const int N = 1e6+5;

int n, anc[N];
ii cont[N];
set<ii> hold;

int root(int u) {
  return anc[u] < 0 ? u : anc[u] = root(anc[u]);
}

void join(int u, int v) {
  if ((u = root(u)) == (v = root(v))) return;
  if (anc[u] > anc[v]) swap(u, v);
  anc[u] += anc[v];
  anc[v] = u;
}

int main() {
  setIO();
  cin >> n;

  foru(i, 1, n) {
    int l, r;
    cin >> l >> r;
    cont[i] = {l, r};
  }

  foru(i, 1, 2*n) {
    anc[i] = -1;
  }

//  hold.insert({3, 1});
//  auto lb = hold.lower_bound({2, 0});
//  cout << lb -> first << "\n";
  sort(cont+1, cont+n+1);
//  foru(i, 1, 2) {
//    int l = cont[i].fi, r = cont[i].se;
//    auto lb = hold.lower_bound({l, 0});
//    if (i == 2) cout << lb -> first << "\n";
//    hold.insert({r, i});
//  }

  foru(i, 1, n) {
    int l = cont[i].fi, r = cont[i].se;
//    cout << l << " " << r << "\n";
    auto lb = hold.lower_bound({l, 0});
    auto rb = hold.lower_bound({r, 0});
//    if (i == 2) {
//      cout << lb -> first << " " << r << "\n";
//        fore(x, hold) cout << x.fi << " " << x.se << "\n";
//    }

    if (lb == hold.end() || lb -> first >= r) {
      hold.insert({r, i});
      continue;
    }

    while (true) {
//      cout << lb -> second << " " << i << "\n";
      join(lb -> second, i + n);
      join(lb -> second + n, i);
      if (lb -> first == prev(rb) -> first) break;
      ++lb;
    }

    hold.insert({r, i});
  }

  int ans = 1;
  foru(i, 1, n) if (root(i) == i) ans = ans * 2 % MOD;
//  foru(i, 1, n) cout << root(i) << " ";
//  cout << "\n";
  cout << ans;
}

Compilation message

port_facility.cpp: In function 'void setIO()':
port_facility.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Incorrect 1 ms 2396 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Incorrect 1 ms 2396 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Incorrect 1 ms 2396 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Incorrect 1 ms 2396 KB Output isn't correct
12 Halted 0 ms 0 KB -