Submission #1062392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062392		kunzaZa183	Port Facility (JOI17_port_facility)	C++17	22 / 100	6041 ms	14840 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
int main() {
  // cin.tie(0)->sync_with_stdio(0);
  // cin.exceptions(cin.failbit);
  int n;
  cin >> n;
  vector<pair<int, int>> vpii(n);
  struct event {
    int tim;
    bool ins;
    int val;
    event() { tim = -1, ins = 0, val = -1; }
    event(int a, int b, int c) { tim = a, ins = b, val = c; }
    bool operator<(event x) const { return tim < x.tim; }
  };
  vector<event> times; // tim id
  for (int i = 0; i < vpii.size(); i++) {
    cin >> vpii[i].first >> vpii[i].second;
    times.emplace_back(vpii[i].first, 1, i);
    times.emplace_back(vpii[i].second, 0, i);
  }
  sort(times.begin(), times.end());

  vector<int> dsu(2 * n);
  iota(dsu.begin(), dsu.end(), 0);
  function<int(int)> par = [&](int cur) {
    if (dsu[cur] == cur)
      return cur;
    dsu[cur] = par(dsu[cur]);
    return dsu[cur];
  };

  struct kun {
    int head, tim;
    kun() { head = 0, tim = 0; }
    kun(int a, int b) { head = a, tim = b; }
    bool operator<(kun x) const { return tim < x.tim; }
  };
  set<kun, less<>> spii; // tim, pile
  for (auto a : times) {
    // cout << a.tim << "\n";
    // for (auto b : spii) {
    //   cout << b.tim << ' ' << b.head << "\n";
    // }

    if (!spii.empty())
      if (spii.begin()->tim < a.tim) {
        spii.erase(spii.begin());
      }

    if (a.ins) {
      kun tmp(a.val, vpii[a.val].second);
      auto it = spii.insert(tmp).first;

      while (1) {
        if (it == spii.begin()) {
          break;
        }
        it--;
        dsu[par(it->head)] = par(tmp.head + n);
        dsu[par(it->head + n)] = par(tmp.head);
        // cout << "NOT " << it->head + 1 << ' ' << tmp.head + 1 << "\n";
      }
    }
  }

  for (int i = 0; i < n; i++)
    if (par(i) == par(i + n)) {
      cout << "0\n";
      return 0;
    }

  set<int> si;
  for (int i = 0; i < 2 * n; i++)
    si.insert(par(i));

  long long ans = 1;
  const int MOD = 1e9 + 7;
  for (int i = 0; i < si.size() / 2; i++) {
    ans *= 2;
    ans %= MOD;
  }

  cout << ans << "\n";
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:18:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for (int i = 0; i < vpii.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
port_facility.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int i = 0; i < si.size() / 2; i++) {
      |                   ~~^~~~~~~~~~~~~~~

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