Submission #1062367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062367		kunzaZa183	Port Facility (JOI17_port_facility)	C++17	0 / 100	0 ms	348 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;
    mutable pair<int, int> dura;
    kun() { head = 0, dura = {0, 0}; }
    kun(int a, int b, int c) { head = a, dura = {b, c}; }
    bool operator<(kun x) const { return dura < x.dura; }
  };
  set<kun, less<>> spii; // tim, pile
  for (auto a : times) {
    // cout << a.tim << "\n";
    // for (auto a : spii) {
    //   cout << a.head << " " << a.dura.first << " " << a.dura.second << "\n";
    // }
    if (!spii.empty()) {
      spii.begin()->dura.first = max(spii.begin()->dura.first, a.tim + 1);
      if (spii.begin()->dura.first > spii.begin()->dura.second) {
        spii.erase(spii.begin());
      }
    }

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

      kun tmp2;
      while (1) {
        if (it == spii.begin())
          break;
        it--;
        dsu[par(it->head)] = par(tmp.head + n);
        dsu[par(it->head + n)] = par(tmp.head);
        tmp2.head = it->head;
        tmp2.dura.second = max(tmp2.dura.second, it->dura.second);
        tmp2.dura.first = it->dura.first;
        it = spii.erase(it);
      }

      spii.insert(tmp2);
      spii.insert(tmp);
    }
  }

  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:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for (int i = 0; i < si.size() / 2; i++) {
      |                   ~~^~~~~~~~~~~~~~~

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