提出 #34620582

---

ソースコード 拡げる

// Author: Ruhan Habib (ruhanhabib39@gmail.com)

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <set>
using namespace std;

const int MX = 1e7;

int N;
set<int> L[MX + 10], R[MX + 10];

int X[MX + 10];

void work () {
   int to_left = 0;

   auto handle = [&] (int x, set<int>& st) {
      for (int i : st) {
         if (!X[i]) X[i] = x;
      }
      to_left += st.size();
      st.clear();
   };

   set<int> avail;
   for (int x = 1; x <= MX; x++) {
      for (int i : L[x]) {
         avail.insert(i);
      }

      if (to_left >= (N + 1) / 2) {
         handle(x, avail);
      } else if (R[x].size()) {
         if (to_left + (int)avail.size() >= (N + 1) / 2) {
            handle(x, avail);
         } else {
            handle(x, R[x]);
         }
      }

      for (int i : R[x]) {
         avail.erase(i);
      }
   }
}

long long work_cost () {
   sort(X, X + N);

   long long ss = accumulate(X, X + N, 0LL);

   long long res = 0;
   for (int i = 0; i < N; i++) {
      res += ss - (N - i) * 1LL * X[i];
      ss -= X[i];
   }

   return res;
}

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);

   cin >> N;
   for (int i = 0; i < N; i++) {
      int l, r; cin >> l >> r;
      L[l].insert(i);
      R[r].insert(i);
   }

   work();

   long long res = work_cost();
   cout << res << "\n";
}

提出情報

ジャッジ結果