Submission #1062426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062426		vjudge1	Port Facility (JOI17_port_facility)	C++17	22 / 100	6088 ms	13500 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:25: 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:25: 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