Submission #1012147


Source Code Expand

/* -------------------------------- Template -------------------------------- */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = std::min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = std::max(a, b); }

struct yes_no : std::numpunct<char> {
  string_type do_truename()  const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};

void solve();

int main() {
  std::locale loc(std::locale(), new yes_no);
  std::cout << std::boolalpha << std::setprecision(12) << std::fixed;
  std::cout.imbue(loc);
  solve();
  return 0;
}

using namespace std;

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;

using key = pair<int,int>;
using tr = tree<key,null_type,less<key>,rb_tree_tag,tree_order_statistics_node_update>;

/* -------------------------------- Library -------------------------------- */

/* ---------------------------------- Main ---------------------------------- */

void merge(tr &a, tr &b) {
  if (a.size() < b.size()) a.swap(b);
  for (auto i: b) a.insert(i);
}

void solve() {
  int N, L;
  cin >> N >> L;
  vector<pair<int,int>> events(N);
  for (auto &i: events) cin >> i.first >> i.second;
  sort(ALL(events));
  vector<vector<int>> ev;
  REP(i,N) {
    if (i == 0 || events[i].first != events[i-1].first)
      ev.push_back({events[i].second});
    else
      ev.back().push_back(events[i].second);
  }
  int c = 0;
  vector<pair<tr,int>> block;
  for (auto &v: ev) {
    const int n = v.size();
    tr t;
    t.clear();
    for (int i: v) t.insert(make_pair(i, c++));
    int mid = t.find_by_order(n / 2)->first;
    block.emplace_back(move(t), mid);

    while (block.size() >= 2) {
      const int m = block.size();
      if (block[m-2].second > block[m-1].second) {
        merge(block[m-2].first, block[m-1].first);
        const int n = block[m-2].first.size();
        block[m-2].second = block[m-2].first.find_by_order(n / 2)->first;
        block.pop_back();
      }
      else break;
    }
  }
  ll res = 0;
  for (auto &i: block) {
    for (auto j: i.first) {
      res += abs(j.first - i.second);
    }
  }
  cout << res << endl;
  return;
}

Submission Info

Submission Time
Task E - 花火
User asi1024
Language C++11 (GCC 4.9.2)
Score 160
Code Size 2974 Byte
Status AC
Exec Time 215 ms
Memory 28500 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 130 / 130
Status
AC × 3
AC × 45
AC × 95
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt, subtask2_40.txt, subtask2_41.txt, subtask2_42.txt, subtask2_43.txt, subtask2_44.txt, subtask2_45.txt, subtask2_46.txt, subtask2_47.txt, subtask2_48.txt, subtask2_49.txt, subtask2_50.txt
Case Name Status Exec Time Memory
sample_01.txt AC 29 ms 924 KB
sample_02.txt AC 31 ms 920 KB
sample_03.txt AC 19 ms 928 KB
subtask1_01.txt AC 19 ms 1180 KB
subtask1_02.txt AC 21 ms 1044 KB
subtask1_03.txt AC 21 ms 1008 KB
subtask1_04.txt AC 21 ms 1180 KB
subtask1_05.txt AC 20 ms 1184 KB
subtask1_06.txt AC 20 ms 1048 KB
subtask1_07.txt AC 21 ms 928 KB
subtask1_08.txt AC 21 ms 1180 KB
subtask1_09.txt AC 20 ms 1184 KB
subtask1_10.txt AC 20 ms 1052 KB
subtask1_11.txt AC 20 ms 920 KB
subtask1_12.txt AC 19 ms 1052 KB
subtask1_13.txt AC 19 ms 1048 KB
subtask1_14.txt AC 20 ms 1048 KB
subtask1_15.txt AC 19 ms 1048 KB
subtask1_16.txt AC 20 ms 1044 KB
subtask1_17.txt AC 19 ms 1308 KB
subtask1_18.txt AC 21 ms 1228 KB
subtask1_19.txt AC 20 ms 1308 KB
subtask1_20.txt AC 21 ms 1172 KB
subtask1_21.txt AC 19 ms 1056 KB
subtask1_22.txt AC 20 ms 1040 KB
subtask1_23.txt AC 21 ms 1180 KB
subtask1_24.txt AC 21 ms 1176 KB
subtask1_25.txt AC 20 ms 1176 KB
subtask1_26.txt AC 21 ms 1308 KB
subtask1_27.txt AC 21 ms 1304 KB
subtask1_28.txt AC 20 ms 1184 KB
subtask1_29.txt AC 20 ms 1176 KB
subtask1_30.txt AC 21 ms 1184 KB
subtask1_31.txt AC 20 ms 1180 KB
subtask1_32.txt AC 21 ms 1048 KB
subtask1_33.txt AC 20 ms 1048 KB
subtask1_34.txt AC 21 ms 1176 KB
subtask1_35.txt AC 21 ms 1184 KB
subtask1_36.txt AC 21 ms 1436 KB
subtask1_37.txt AC 19 ms 924 KB
subtask1_38.txt AC 19 ms 920 KB
subtask1_39.txt AC 29 ms 924 KB
subtask1_40.txt AC 34 ms 924 KB
subtask1_41.txt AC 19 ms 924 KB
subtask1_42.txt AC 19 ms 792 KB
subtask2_01.txt AC 185 ms 12508 KB
subtask2_02.txt AC 189 ms 12364 KB
subtask2_03.txt AC 181 ms 11612 KB
subtask2_04.txt AC 178 ms 11480 KB
subtask2_05.txt AC 191 ms 11996 KB
subtask2_06.txt AC 147 ms 9560 KB
subtask2_07.txt AC 104 ms 6812 KB
subtask2_08.txt AC 72 ms 4700 KB
subtask2_09.txt AC 186 ms 12972 KB
subtask2_10.txt AC 173 ms 11604 KB
subtask2_11.txt AC 149 ms 12504 KB
subtask2_12.txt AC 163 ms 12880 KB
subtask2_13.txt AC 179 ms 11740 KB
subtask2_14.txt AC 168 ms 14608 KB
subtask2_15.txt AC 129 ms 11936 KB
subtask2_16.txt AC 118 ms 8672 KB
subtask2_17.txt AC 142 ms 9380 KB
subtask2_18.txt AC 162 ms 8928 KB
subtask2_19.txt AC 156 ms 14436 KB
subtask2_20.txt AC 106 ms 14620 KB
subtask2_21.txt AC 100 ms 12780 KB
subtask2_22.txt AC 117 ms 8480 KB
subtask2_23.txt AC 146 ms 8668 KB
subtask2_24.txt AC 130 ms 18516 KB
subtask2_25.txt AC 144 ms 23244 KB
subtask2_26.txt AC 130 ms 13652 KB
subtask2_27.txt AC 142 ms 15056 KB
subtask2_28.txt AC 146 ms 11428 KB
subtask2_29.txt AC 114 ms 13344 KB
subtask2_30.txt AC 111 ms 13088 KB
subtask2_31.txt AC 110 ms 13340 KB
subtask2_32.txt AC 140 ms 13012 KB
subtask2_33.txt AC 150 ms 15316 KB
subtask2_34.txt AC 105 ms 10400 KB
subtask2_35.txt AC 123 ms 13272 KB
subtask2_36.txt AC 143 ms 15652 KB
subtask2_37.txt AC 139 ms 14168 KB
subtask2_38.txt AC 148 ms 28500 KB
subtask2_39.txt AC 167 ms 14444 KB
subtask2_40.txt AC 157 ms 14624 KB
subtask2_41.txt AC 128 ms 22736 KB
subtask2_42.txt AC 129 ms 19156 KB
subtask2_43.txt AC 215 ms 13392 KB
subtask2_44.txt AC 181 ms 14624 KB
subtask2_45.txt AC 188 ms 18644 KB
subtask2_46.txt AC 166 ms 14612 KB
subtask2_47.txt AC 144 ms 28496 KB
subtask2_48.txt AC 19 ms 800 KB
subtask2_49.txt AC 18 ms 792 KB
subtask2_50.txt AC 18 ms 788 KB