結果
| 問題 | No.738 平らな農地 |
| ユーザー |
 furuya1223
|
| 提出日時 | 2019-10-07 11:51:25 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 15,652 bytes |
| コンパイル時間 | 1,947 ms |
| コンパイル使用メモリ | 152,648 KB |
| 実行使用メモリ | 563,308 KB |
| 最終ジャッジ日時 | 2024-10-12 21:00:40 |
| 合計ジャッジ時間 | 17,792 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
10,496 KB |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,248 KB |
| testcase_03 | AC | 2 ms
5,248 KB |
| testcase_04 | AC | 2 ms
5,248 KB |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | RE | - |
| testcase_28 | RE | - |
| testcase_29 | RE | - |
| testcase_30 | RE | - |
| testcase_31 | RE | - |
| testcase_32 | RE | - |
| testcase_33 | RE | - |
| testcase_34 | RE | - |
| testcase_35 | RE | - |
| testcase_36 | RE | - |
| testcase_37 | RE | - |
| testcase_38 | RE | - |
| testcase_39 | RE | - |
| testcase_40 | RE | - |
| testcase_41 | RE | - |
| testcase_42 | RE | - |
| testcase_43 | RE | - |
| testcase_44 | RE | - |
| testcase_45 | RE | - |
| testcase_46 | RE | - |
| testcase_47 | RE | - |
| testcase_48 | RE | - |
| testcase_49 | RE | - |
| testcase_50 | RE | - |
| testcase_51 | RE | - |
| testcase_52 | RE | - |
| testcase_53 | RE | - |
| testcase_54 | RE | - |
| testcase_55 | RE | - |
| testcase_56 | RE | - |
| testcase_57 | RE | - |
| testcase_58 | RE | - |
| testcase_59 | RE | - |
| testcase_60 | RE | - |
| testcase_61 | RE | - |
| testcase_62 | RE | - |
| testcase_63 | RE | - |
| testcase_64 | RE | - |
| testcase_65 | RE | - |
| testcase_66 | RE | - |
| testcase_67 | RE | - |
| testcase_68 | RE | - |
| testcase_69 | RE | - |
| testcase_70 | RE | - |
| testcase_71 | AC | 38 ms
5,580 KB |
| testcase_72 | RE | - |
| testcase_73 | MLE | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
ソースコード
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdint>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <sys/timeb.h>
#include <vector>
using namespace std;
#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define reprrev(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define reprev(i, n) reprrev(i, 0, n)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define chmin(mi, val) mi = min(mi, val)
#define chmax(ma, val) ma = max(ma, val)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define mp make_pair
#define mt make_tuple
#define INF 1050000000
#define INFR INT_MAX
#define INFL (long long)(4e18)
#define INFLR LLONG_MAX
#define EPS (1e-10)
#define MOD 1000000007
//#define MOD 998244353
#define PI 3.141592653589793238
#define RMAX 4294967295
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vvvvi = vector<vector<vector<vector<int>>>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvc = vector<vector<char>>;
using vs = vector<string>;
using vvs = vector<vector<string>>;
using Pi = pair<int, int>;
using vPi = vector<Pi>;
using vvPi = vector<vector<Pi>>;
using vvvPi = vector<vector<vector<Pi>>>;
using vvvvPi = vector<vector<vector<vector<Pi>>>>;
using Pll = pair<ll, ll>;
using vPll = vector<Pll>;
using Pd = pair<double, double>;
using vPd = vector<Pd>;
template <class T>
using vec = vector<T>;
template <class T>
using pql = priority_queue<T, vector<T>, greater<T>>;
using Comp = complex<double>;
// vvvvvvvvvvvvvvvvvvvvvvv debug output vvvvvvvvvvvvvvvvvvvvvvv
// vector input
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
for (T &x : vec) is >> x;
return is;
}
// pair
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var) {
os << "(" << pair_var.first << ", " << pair_var.second << ")";
return os;
}
// vector
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
os << "{";
for (int i = 0; i < vec.size(); i++) {
os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
}
os << "}";
return os;
}
// deque
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &vec) {
os << "{";
for (int i = 0; i < vec.size(); i++) {
os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
}
os << "}";
return os;
}
// map
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
os << "{";
repi(itr, map_var) {
os << *itr;
itr++;
if (itr != map_var.end()) os << ", ";
itr--;
}
os << "}";
return os;
}
// set
template <typename T>
ostream &operator<<(ostream &os, const set<T> &set_var) {
os << "{";
repi(itr, set_var) {
os << *itr;
itr++;
if (itr != set_var.end()) os << ", ";
itr--;
}
os << "}";
return os;
}
// multiset
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &set_var) {
os << "{";
repi(itr, set_var) {
os << *itr;
itr++;
if (itr != set_var.end()) os << ", ";
itr--;
}
os << "}";
return os;
}
#define DUMPOUT cerr
void dump_func() {
DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head &&head, Tail &&... tail) {
DUMPOUT << head;
if (sizeof...(Tail) > 0) {
DUMPOUT << ", ";
}
dump_func(std::move(tail)...);
}
#ifdef DEBUG_
#define DEB
#define dump(...) \
DUMPOUT << " " << string(#__VA_ARGS__) << ": " \
<< "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" \
<< endl \
<< " ", \
dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
// ^^^^^^^^^^^^^^^^^^^^^^^ debug output ^^^^^^^^^^^^^^^^^^^^^^^
string YN(bool y, int id = 0) {
if (id) cout << id;
return (y ? "YES" : "NO");
}
string yn(bool y, int id = 0) {
if (id) cout << id;
return (y ? "Yes" : "No");
}
string ON(bool y, int id = 0) {
if (id) cout << id;
return (y ? "OK" : "NG");
}
int dir4[4][2] = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};
int dir8[8][2] = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0},
{1, 0}, {-1, 1}, {0, 1}, {1, 1}};
char dirchar[4] = {'<', '^', '>', 'v'};
// [a,b)
int irand(int a, int b) {
static mt19937 Rand(static_cast<unsigned int>(time(nullptr)));
uniform_int_distribution<int> dist(a, b - 1);
return dist(Rand);
}
// [a,b)
double drand(int a, int b) {
static mt19937 Rand(static_cast<unsigned int>(time(nullptr)));
uniform_real_distribution<double> dist(a, b);
return dist(Rand);
}
// https://qiita.com/IgnorantCoder/items/3101d6276e9bdddf872c
template <typename A, typename F>
inline auto transform(const A &v, F &&f) {
using result_type =
decltype(std::declval<F>()(std::declval<typename A::value_type>()));
vector<result_type> y(v.size());
std::transform(std::cbegin(v), std::cend(v), std::begin(y), f);
return y;
}
// 多次元vector生成
template <class T>
vector<T> make_v(size_t size, const T &init) {
return vector<T>(size, init);
}
template <class... Ts>
auto make_v(size_t size, Ts... rest) {
return vector<decltype(make_v(rest...))>(size, make_v(rest...));
}
template <typename T>
T Max(vector<T> a) {
return *max_element(all(a));
}
template <typename T>
T Min(vector<T> a) {
return *min_element(all(a));
}
template <typename T>
T Sum(vector<T> a) {
return accumulate(all(a), (T)0);
}
// mapでカウントとかする
template <typename T>
void Add(map<T, int> &m, T item) {
if (m.find(item) == m.end()) {
m[item] = 1;
} else {
m[item]++;
}
}
// mapでカウントとかする
template <typename T>
void Erase(map<T, int> &m, T item) {
if (m.find(item) == m.end()) {
} else {
if (m[item] == 1) {
m.erase(item);
} else {
m[item]--;
}
}
}
// デフォルト値つきのmapのget
template <typename T, typename U>
U Get(map<T, U> m, T key, U def) {
if (m.find(key) == m.end()) {
return def;
} else {
return m[key];
}
}
template <typename T>
inline bool Contains(const set<T> &t, const T &key) {
return t.find(key) != t.end();
}
template <typename T, typename U>
inline bool Contains(const map<T, U> &t, const T &key) {
return t.find(key) != t.end();
}
template <class T>
struct Edge {
int from, to;
T cost;
bool operator<(Edge e) {
return cost < e.cost;
}
};
template <class T>
ostream &operator<<(ostream &os, Edge<T> &edge) {
os << "(" << edge.from << "->" << edge.to << ":" << edge.cost << ")";
return os;
}
template <class T = int>
class Graph {
int n;
bool directed;
vector<vector<Edge<T>>> edges;
public:
Graph(int n, bool directed)
: n(n), directed(directed), edges(vector<vector<Edge<T>>>(n)) {}
void add_edge(int s, int t, T cost) {
edges[s].push_back(Edge<T>{s, t, cost});
if (!directed) {
edges[t].push_back(Edge<T>{t, s, cost});
}
}
Graph() {}
vector<Edge<T>> operator[](size_t i) const {
return edges[i];
}
int size() const {
return n;
}
};
//======================================================
class BitVector {
vector<int> cumulative_sum;
int pos = 1;
vector<int> pos_select;
public:
vector<vector<int>> select; // select[b][n] = n 番目（0-indexed）の b の位置
BitVector(int n)
: cumulative_sum(n + 1), pos_select(2, 0), select(2, vector<int>(n)) {
cumulative_sum[0] = 0;
}
// 数 b を追加。n 回呼ばれる
void push(int b) {
cumulative_sum[pos] = cumulative_sum[pos - 1] + b;
select[b][pos_select[b]] = pos - 1;
pos++;
pos_select[b]++;
}
int operator[](int idx) const {
return cumulative_sum[idx + 1] - cumulative_sum[idx];
}
// [0, n) に x がいくつあるか
int rank(int n, int b) const {
if (n < 0) return 0;
n = min(n, size());
if (b == 1) {
return cumulative_sum[n];
} else {
return n - cumulative_sum[n];
}
}
int size() const {
return cumulative_sum.size() - 1;
}
};
ostream &operator<<(ostream &os, const BitVector &bv) {
os << "{";
for (int i = 0; i < bv.size(); i++) {
os << bv[i] << (i + 1 == bv.size() ? "" : ", ");
}
os << "}";
return os;
}
class WaveletMatrix {
int len; // 数列の長さ
int digit = 0; // 値の桁数
vector<BitVector> bit_vectors;
vector<int> num_zero;
vector<int> start;
vector<int> sorted;
public:
WaveletMatrix(vector<int> v) {
len = v.size();
int max_value = *max_element(all(v));
while (max_value > 0) {
max_value >>= 1;
digit++;
}
if (digit == 0) digit++;
start = vector<int>(1 << digit, -1);
bit_vectors.reserve(digit);
num_zero = vector<int>(digit, 0);
rep(d, digit) {
bit_vectors.emplace_back(len);
rep(i, len) {
bit_vectors[d].push(v[i] >> (digit - 1 - d) & 1);
}
vector<int> temp;
temp.reserve(len);
rep(i, len) {
if ((v[i] >> (digit - 1 - d) & 1) == 0) {
temp.push_back(v[i]);
num_zero[d]++;
}
}
rep(i, len) {
if ((v[i] >> (digit - 1 - d) & 1) == 1) {
temp.push_back(v[i]);
}
}
v = temp;
}
reprev(i, len) {
start[v[i]] = i;
}
sorted = v;
}
// n 番目（0-indexed）の値を得る
int operator[](int n) const {
int ans = 0;
rep(d, digit) {
ans <<= 1;
ans += bit_vectors[d][n];
if (bit_vectors[d][n] == 1) {
n = num_zero[d] + bit_vectors[d].rank(n, 1);
} else {
n = bit_vectors[d].rank(n, 0);
}
}
return ans;
}
// [0, n) に x がいくつ含まれるか
int rank(int n, int x) {
if (start[x] == -1) return 0;
rep(d, digit) {
if ((x >> (digit - 1 - d) & 1) == 1) {
n = num_zero[d] + bit_vectors[d].rank(n, 1);
} else {
n = bit_vectors[d].rank(n, 0);
}
}
return n - start[x];
}
// n 番目（0-indexed）の x の位置（無ければ-1）
int select(int n, int x) {
if (start[x] == -1 || sorted[start[x] + n] != x) return -1;
n = start[x] + n;
reprev(d, digit) {
if ((x >> (digit - 1 - d) & 1) == 1) {
n = bit_vectors[d].select[1][n - num_zero[d]];
} else {
n = bit_vectors[d].select[0][n];
}
}
return n;
}
// [l, r) で n 番目（0-indexed）に小さい値
int quantile(int l, int r, int n) {
rep(d, digit) {
if (bit_vectors[d].rank(r, 0) - bit_vectors[d].rank(l, 0) > n) {
// 0
l = bit_vectors[d].rank(l, 0);
r = bit_vectors[d].rank(r, 0);
} else {
// 1
n -= bit_vectors[d].rank(r, 0) - bit_vectors[d].rank(l, 0);
l = num_zero[d] + bit_vectors[d].rank(l, 1);
r = num_zero[d] + bit_vectors[d].rank(r, 1);
}
}
return sorted[l];
}
// [l, r) で出現回数が多い順に k 個の値と頻度を返す
vector<pair<int, int>> topk(int l, int r, int k) {
vector<pair<int, int>> res;
res.reserve(k);
priority_queue<tuple<int, int, int, int>> pq;
pq.push(mt(r - l, 0, l, r));
while (!pq.empty() && res.size() < k) {
int dummy, d;
tie(dummy, d, l, r) = pq.top();
pq.pop();
if (d == digit) {
// 終わり
res.push_back(mp(sorted[l], r - l));
continue;
}
int l0 = bit_vectors[d].rank(l, 0);
int r0 = bit_vectors[d].rank(r, 0);
int l1 = num_zero[d] + bit_vectors[d].rank(l, 1);
int r1 = num_zero[d] + bit_vectors[d].rank(r, 1);
pq.push(mt(r0 - l0, d + 1, l0, r0));
pq.push(mt(r1 - l1, d + 1, l1, r1));
}
return res;
}
// [l, r) に含まれる x 未満の値の個数
int less_freq(int l, int r, int x) {
if (x <= 0) return 0;
if (l >= r) return 0;
int ans = 0;
rep(d, digit) {
if ((x >> (digit - 1 - d) & 1) == 1) {
ans += bit_vectors[d].rank(r, 0) - bit_vectors[d].rank(l, 0);
l = num_zero[d] + bit_vectors[d].rank(l, 1);
r = num_zero[d] + bit_vectors[d].rank(r, 1);
} else {
l = bit_vectors[d].rank(l, 0);
r = bit_vectors[d].rank(r, 0);
}
}
return ans;
}
// [l, r) に含まれる [a, b) の範囲の値の和
long long range_sum(int l, int r, int a, int b) {
long long ans = 0;
priority_queue<tuple<int, int, int, int>> pq;
pq.push(mt(r - l, 0, l, r));
while (!pq.empty()) {
int dummy, d;
tie(dummy, d, l, r) = pq.top();
pq.pop();
if (d == digit) {
// 終わり
if (a <= sorted[l] && sorted[l] < b) {
ans += (long long)sorted[l] * (r - l);
}
continue;
}
int l0 = bit_vectors[d].rank(l, 0);
int r0 = bit_vectors[d].rank(r, 0);
int l1 = num_zero[d] + bit_vectors[d].rank(l, 1);
int r1 = num_zero[d] + bit_vectors[d].rank(r, 1);
pq.push(mt(r0 - l0, d + 1, l0, r0));
pq.push(mt(r1 - l1, d + 1, l1, r1));
}
return ans;
}
};
int main() {
int N, K;
cin >> N >> K;
vi A(N);
cin >> A;
WaveletMatrix wm(A);
ll ans = INFL;
rep(i, N - K + 1) {
// [i, i+K) で揃えるコスト
int median = wm.quantile(i, i + K, K / 2);
int less_num = wm.less_freq(i, i + K, median);
int more_num = K - less_num;
int less_sum = wm.range_sum(i, i + K, 0, median);
int more_sum = wm.range_sum(i, i + K, median, INF);
ll cost = 0;
cost += (ll)median * less_num - less_sum;
cost += more_sum - (ll)median * more_num;
chmin(ans, cost);
dump(i, median, less_num, more_num, less_sum, more_sum, cost);
}
cout << ans << endl;
return 0;
}