結果
| 問題 |
No.738 平らな農地
|
| ユーザー |
 hamray
|
| 提出日時 | 2021-01-02 18:38:44 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 324 ms / 2,000 ms |
| コード長 | 11,890 bytes |
| コンパイル時間 | 2,202 ms |
| コンパイル使用メモリ | 192,368 KB |
| 実行使用メモリ | 53,548 KB |
| 最終ジャッジ日時 | 2024-10-12 08:35:08 |
| 合計ジャッジ時間 | 16,464 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 87 |
ソースコード
#include <bits/stdc++.h>
//#include <atcoder/all>
//using namespace atcoder;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define MOD 1000000007
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
const double EPS = 1e-9, PI = acos(-1);
const double pi = 3.141592653589793238462643383279;
//ここから編集
typedef string::const_iterator State;
ll GCD(ll a, ll b){
return (b==0)?a:GCD(b, a%b);
}
ll LCM(ll a, ll b){
return a/GCD(a, b) * b;
}
template< int mod >
struct ModInt {
int x;
ModInt() : x(0) {}
ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
ModInt &operator+=(const ModInt &p) {
if((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int) (1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while(b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
ModInt pow(int64_t n) const {
ModInt ret(1), mul(x);
while(n > 0) {
if(n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ModInt &a) {
int64_t t;
is >> t;
a = ModInt< mod >(t);
return (is);
}
static int get_mod() { return mod; }
};
using modint = ModInt< 998244353 >;
template< typename T >
struct Combination {
vector< T > _fact, _rfact, _inv;
Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
_fact[0] = _rfact[sz] = _inv[0] = 1;
for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
_rfact[sz] /= _fact[sz];
for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
}
inline T fact(int k) const { return _fact[k]; }
inline T rfact(int k) const { return _rfact[k]; }
inline T inv(int k) const { return _inv[k]; }
T P(int n, int r) const {
if(r < 0 || n < r) return 0;
return fact(n) * rfact(n - r);
}
T C(int p, int q) const {
if(q < 0 || p < q) return 0;
return fact(p) * rfact(q) * rfact(p - q);
}
T H(int n, int r) const {
if(n < 0 || r < 0) return (0);
return r == 0 ? 1 : C(n + r - 1, r);
}
};
struct WaveletMatrix {
struct BitVector{
// 大ブロックを 256, 小ブロックを8としておく
const uint64_t BLOCK_BITNUM = 256;
const uint64_t TABLE_INTERVAL = 8;
const uint64_t NOT_FOUND = 0xFFFFFFFFFFFFFFFFLLU; /* selectで使う */
uint64_t length;
vector<uint64_t> bits; /* 元のbit列を圧縮したもの */
vector<uint32_t> blocks; /* 1つ目の補助データに該当するもの */
vector<uint64_t> tables; /* 2つ目の補助データに該当するもの */
BitVector() : length(0){}
BitVector(uint64_t N){
init(N);
}
void init(uint64_t N) {
length = N;
uint64_t block_num = (N + BLOCK_BITNUM - 1) / (BLOCK_BITNUM);
blocks.assign(block_num+1,0);
uint64_t bits_len = (N + TABLE_INTERVAL - 1) / (TABLE_INTERVAL);
bits.assign(bits_len+1,0);
tables.assign(bits_len+1,0);
//cerr << blocks.size() << " " << bits.size() << endl;
}
void build(){
uint64_t block_ind, offset, table_ind, sz = (length + BLOCK_BITNUM - 1) / (BLOCK_BITNUM);
blocks[0] = 0;
for(block_ind=0; block_ind < sz; block_ind++){
tables[block_ind * BLOCK_BITNUM / TABLE_INTERVAL] = 0;
table_ind = (block_ind * BLOCK_BITNUM) / TABLE_INTERVAL;
for(offset=0; offset<BLOCK_BITNUM && table_ind+1 < tables.size() ; offset+=TABLE_INTERVAL){
/* 現在見る位置はblock_ind * BLOCK_BITNUM + offset */
tables[table_ind + 1] = tables[table_ind] + __builtin_popcountll(bits[table_ind]);
table_ind++;
}
blocks[block_ind + 1] = blocks[block_ind] + tables[table_ind];
}
if(block_ind * BLOCK_BITNUM / TABLE_INTERVAL < tables.size())
tables[block_ind * BLOCK_BITNUM / TABLE_INTERVAL] = 0;
}
void set(uint64_t b, uint64_t pos){
assert(pos >= 0 && pos < length);
uint64_t block_ind = pos / TABLE_INTERVAL;
uint64_t offset = pos % TABLE_INTERVAL;
if(b == 1) bits[block_ind] |= (1UL << offset);
else bits[block_ind] &= ~(1UL << offset);
}
int access(uint64_t pos){
assert(pos >= 0 && pos < length);
uint64_t block_ind = pos / TABLE_INTERVAL;
uint64_t offset = pos % TABLE_INTERVAL;
return (bits[block_ind] >> offset) & 1;
}
/* [0,pos)の1の数 */
uint64_t rank(uint64_t bit, uint64_t pos){
uint64_t block_ind = pos / BLOCK_BITNUM;
uint64_t table_ind = pos / TABLE_INTERVAL;
uint64_t offset = pos % TABLE_INTERVAL;
uint64_t m = (bits[table_ind] & ((1UL << offset) - 1));
return bit ? blocks[block_ind] + tables[table_ind] + __builtin_popcountll(m) : pos - rank(1,pos);
}
uint64_t rank(uint64_t bit, uint64_t l, uint64_t r){
return rank(bit, r) - rank(bit, l);
}
};
uint64_t length;
uint64_t height;
uint64_t sigma;
vector<BitVector> B; /* 各高さの索引 */
vector<uint64_t> zerosum; /* 各高さにおける0の数 */
vector<vector<uint64_t>> cums;
WaveletMatrix(){}
WaveletMatrix(vector<uint64_t> v, uint64_t _sigma) :length(v.size()), sigma(_sigma) {
height = (sigma == 1) ? 1 : (64 - __builtin_clzll(sigma-1));
B.resize(height); zerosum.resize(height), cums.resize(height);
for(int i=0; i<height; i++){
B[i].init(v.size());
cums[i].resize(v.size()+1);
vector<uint64_t> v0, v1;
for(int j=0; j<v.size(); j++){
int bi_j = (v[j] >> (height - 1 - i)) & 1;
B[i].set(bi_j, j);
if(bi_j == 0) v0.emplace_back(v[j]);
else v1.emplace_back(v[j]);
cums[i][j+1] = cums[i][j] + v[j];
}
zerosum[i] = v0.size();
for(int j=0; j<v1.size(); j++) v0.emplace_back(v1[j]);
B[i].build();
// for(int j=0; j<v.size(); j++) cout << B[i].access(j);
// cout << endl;
v = move(v0);
}
}
int access(int pos){
assert(pos >= 0 && pos < length);
uint64_t res = 0;
for(int i=0; i<height; i++){
int bit = B[i].access(pos);
//cout << bit << endl;
if(bit) res |= (1UL << (height - 1 - i));
pos = B[i].rank(bit, pos);
if(bit) pos += zerosum[i];
}
return res;
}
/* [0,r)のcの数 */
int rank(uint64_t c, int r){
if(c >= sigma) return 0;
int l = 0;
for(int i=0; i<height; i++){
int bit = ((c >> (height - 1 - i)) & 1);
l = (bit?zerosum[i]:0) + B[i].rank(bit, l);
r = (bit?zerosum[i]:0) + B[i].rank(bit, r);
}
return r-l;
}
/* [l, r)のcの数 */
int rank(uint64_t c, int l, int r){
if(c >= sigma) return 0;
for(int i=0; i<height; i++){
int bit = ((c >> (height - 1 - i)) & 1);
l = (bit?zerosum[i]:0) + B[i].rank(bit, l);
r = (bit?zerosum[i]:0) + B[i].rank(bit, r);
}
return r-l;
}
/* [l, r)でk(=0,1,...,r-l-1)番目に小さい値を返す */
/* verify:https://old.yosupo.jp/problem/range_kth_smallest*/
uint64_t kth_smallest(int l, int r, int k) {
uint64_t res = 0;
for(int i=0; i<height; i++){
int num = B[i].rank(0, l, r);
if(k < num){
l = B[i].rank(0, l);
r = B[i].rank(0, r);
}else{
l = zerosum[i] + B[i].rank(1, l);
r = zerosum[i] + B[i].rank(1, r);
k -= num;
res |= (1UL << (height - 1 - i));
}
}
return res;
}
uint64_t kth_largest(int l, int r, int k){
return kth_smallest(l, r, r-l-k-1);
}
/* [l, r)中でx未満の要素の数を返す */
uint64_t rank_lower(int l, int r, uint64_t x){
uint64_t res = 0;
for(int i=0; i<height; i++){
int bit = (x >> (height - 1 - i) & 1);
if(bit == 0){
l = B[i].rank(0, l);
r = B[i].rank(0, r);
}else{
res += B[i].rank(0, l, r);
l = zerosum[i] + B[i].rank(1, l);
r = zerosum[i] + B[i].rank(1, r);
}
}
return res;
}
/* [l, r)中でx以上y未満の要素の数を返す */
/* verify:https://codeforces.com/contest/1042/problem/D */
uint64_t range_freq(int l, int r, uint64_t x, uint64_t y) {
return rank_lower(l, r, y) - rank_lower(l, r, x);
}
/* [l, r)中でv < xを満たす最大のvを返す */
/* verigy:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1549*/
uint64_t prev_value(int l, int r, uint64_t x) {
uint64_t cnt = rank_lower(l, r, x);
return cnt == 0 ? 1e9 : kth_smallest(l, r, cnt - 1);
}
/* [l, r)中でx <= vを満たす最小のvを返す */
/* verigy:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1549*/
uint64_t next_value(int l, int r, uint64_t x) {
uint64_t cnt = rank_lower(l, r, x);
return cnt == r-l ? 1e9 : kth_smallest(l, r, cnt);
}
};
template<typename T = int> struct BIT{
vector<T> node;
int N;
BIT(int n){
N = n;
node.resize(N+1);
}
void add(int i, T x){
i++;
while(i <= N){
node[i] += x;
i += (i & -i);
}
}
T sum(int i){
T res = 0;
while(i > 0){
res += node[i];
i -= (i & -i);
}
return res;
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(12);
int N, K; cin >> N >> K;
vector<uint64_t> a(N);
BIT<ll> sums(1010101), tot(1010101);
REP(i,N) cin >> a[i];
vector<ll> v;
REP(i,N){
v.push_back(a[i]);
}
sort(all(v));
v.erase(unique(all(v)), v.end());
WaveletMatrix wm(a, *max_element(all(a)) + 1);
REP(i,N) a[i] = lower_bound(all(v), a[i]) - v.begin();
for(int i=0; i<K-1; i++) {
sums.add(a[i]+1, v[a[i]]);
tot.add(a[i]+1, 1);
}
ll ans = (1LL<<60);
for(int i=0; i+K<=N; i++){
sums.add(a[i+K-1]+1, v[a[i+K-1]]);
tot.add(a[i+K-1]+1, 1);
ll c = wm.kth_smallest(i, i+K, K/2);
int idx = upper_bound(all(v), c) - v.begin();
ll t1 = sums.sum(idx);
ll t2 = sums.sum(1010101) - sums.sum(idx);
//cout << sums.sum(1010101) << " " << t1 << " " << t2 << endl;
ll n1 = tot.sum(idx);
ll n2 = tot.sum(1010101) - tot.sum(idx);
ans = min(ans, abs(t1 - c * n1) + abs(t2 - c * n2));
sums.add(a[i]+1, -v[a[i]]);
tot.add(a[i]+1, -1);
}
cout << ans << endl;
return 0;
}