結果

問題 No.738 平らな農地
ユーザー たこし
提出日時 2018-09-28 22:39:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,051 ms / 2,000 ms
コード長 8,012 bytes
コンパイル時間 2,220 ms
コンパイル使用メモリ 215,748 KB
最終ジャッジ日時 2025-01-06 13:57:31
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 87
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#include <cstdio>
#include <string>
using namespace std;
#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double
class Node {
public:
Node(unsigned long long int lIndex = startLeftIndex, unsigned long long int rIndex = endRightIndex, LL v = unitValue) : leftIndex(lIndex),
        rightIndex(rIndex), value(v) {
}
Node operator + (const Node& monoid) const {
return Node(startLeftIndex, endRightIndex, this->getValue() + monoid.getValue());
}
static Node unit() {
return Node(unitValue);
}
void setValue(LL l) {
this->value = l;
}
LL getValue() const {
return this->value;
}
pair<LL, LL> getIndexRange() {
return make_pair(leftIndex, rightIndex);
}
bool isLeafNode() {
auto it = getIndexRange();
return it.second - it.first <= 1;
}
//
void setValue(unsigned long long int index, LL value) {
auto indexRange = getIndexRange();
unsigned long long int leftIndex = indexRange.first, midIndex = (indexRange.first + indexRange.second)/2, rightIndex = indexRange.second;
if(isLeafNode()) {
if(leftIndex <= index && index < rightIndex) {
setValue(value);
}
return;
}
if(!left_child) {
left_child = unique_ptr<Node>(new Node(leftIndex, midIndex));
}
if(!right_child) {
right_child = unique_ptr<Node>(new Node(midIndex, rightIndex));
}
if(leftIndex <= index && index < midIndex) {
left_child->setValue(index, value);
} else {
right_child->setValue(index, value);
}
//
Node lNode, rNode; lNode.setValue(left_child->getValue()); rNode.setValue(right_child->getValue());
setValue((lNode + rNode).getValue());
}
LL query(unsigned long long int l, unsigned long long int r) {
auto indexRange = getIndexRange();
if(l <= indexRange.first && indexRange.second <= r) {
return getValue();
} else if(indexRange.second <= l || r <= indexRange.first) {
return Node::unit().getValue();
} else {
LL ll = Node::unit().getValue(), rr = Node::unit().getValue();
if(left_child) {
ll = left_child->query(l, r);
}
if(right_child) {
rr = right_child->query(l, r);
}
Node lNode, rNode;
lNode.setValue(ll); rNode.setValue(rr);
return (lNode + rNode).getValue();
}
}
private:
LL value;
static const LL unitValue = 0;
static const LL startLeftIndex = 0, endRightIndex = 1145141919810;
unique_ptr<Node> left_child, right_child;
unsigned long long int leftIndex, rightIndex;
};
template <class T>
class SegmentTree {
public:
SegmentTree() {
root = unique_ptr<Node>(new Node());
}
void setValue(unsigned long long int index, LL value) {
root->setValue(index, value);
}
LL query(unsigned long long int l, unsigned long long int r) {
return root->query(l, r);
}
private:
unique_ptr<T> root;
};
#define int long long
typedef pair<LL, int> Key;
typedef int Value;
struct Treap{
Key key; //
Value value; //
Treap *ch[2]; //
int pri; //
int cnt; //
int sum; //
Treap(const Key &key, const Value &value) : key(key), value(value), pri(rand()), cnt(1), sum(value) {
ch[0] = ch[1] = NULL;
}
};
//
int countTreap(Treap *t){return !t ? 0 : t->cnt;}
//
int sumTreap(Treap *t){return !t ? 0 : t->sum;}
//
//
Treap *updateTreap(Treap *t){
t->cnt = countTreap(t->ch[0]) + countTreap(t->ch[1]) + 1;
t->sum = sumTreap(t->ch[0]) + sumTreap(t->ch[1]) + t->value;
return t;
}
//b:0  1
Treap *rotateTreap(Treap *t, int b){
Treap *s = t->ch[1-b];
t->ch[1-b] = s->ch[b];
s->ch[b] = t;
updateTreap(t); updateTreap(s);
return s;
}
//t(key, value)
Treap *insertTreap(Treap *t, const Key &key, const Value &value){
if(!t) return new Treap(key, value);
else if(key == t->key) return t;
int b = !(key < t->key);
t->ch[b] = insertTreap(t->ch[b], key, value);
updateTreap(t);
//
if(t->pri < t->ch[b]->pri)
t = rotateTreap(t, 1-b);
return t;
}
//key
Treap *findTreap(Treap *t, const Key &key){
return !t || key == t->key ? t : findTreap(t->ch[t->key < key], key);
}
//index(0-index)
Treap *findIndexTreap(Treap *t, int index = 0){
//NULLindex
if(!t || t->cnt <= index) return NULL;
if(t->ch[0]){
if(index < t->ch[0]->cnt){
return findIndexTreap(t->ch[0], index);
}
else{
index = index - (t->ch[0]->cnt);
if(index == 0)
return t;
else
return findIndexTreap(t->ch[1], index-1);
}
}
else if(t->ch[1]){
if(index == 0)
return t;
else
return findIndexTreap(t->ch[1], index - 1);
}
else{
if(index == 0)
return t;
else
return NULL;
}
}
//key
Treap *eraseTreap(Treap *t, const Key &key){
if(!t)
return NULL;
if(key == t->key){
if(!t->ch[0] && !t->ch[1]){
//t
return NULL;
}
else if(!t->ch[0])
t = rotateTreap(t, 0);
else if(!t->ch[1])
t = rotateTreap(t, 1);
else
t = rotateTreap(t, !(t->ch[0]->pri < t->ch[1]->pri));
t = eraseTreap(t, key);
}
else{
int b = !(key < t->key);
t->ch[b] = eraseTreap(t->ch[b], key);
}
updateTreap(t);
return t;
}
const int MAX_N = 100005;
const int MAX_K = 100005;
int N, K;
int A[MAX_N];
SegmentTree<Node> segmentTree;
SegmentTree<Node> segmentTreeCount;
signed main()
{
Treap *root = NULL;
cin >> N >> K;
for(int i = 0; i < N; i++) {
cin >> A[i];
}
int sum = 0;
int ans = 1145141919810364;
for(int i = 0; i < N; i++) {
sum += A[i];
root = insertTreap(root, Key(A[i], i), A[i]);
segmentTree.setValue(A[i], segmentTree.query(A[i], A[i]+1) + A[i]);
segmentTreeCount.setValue(A[i], segmentTreeCount.query(A[i], A[i]+1)+1);
if(countTreap(root) == K) {
Treap *t = findIndexTreap(root, (K-1)/2);
int mid = t->value;
int L = 0, R = 0;
int lCount = segmentTreeCount.query(0, mid);
int rCount = segmentTreeCount.query(mid+1, 1e9+7);
L = mid*lCount - segmentTree.query(0, mid);
R = segmentTree.query(mid+1, 1e9+7) - mid*rCount;
// cerr << i << " " << L << " " << R << endl;
// cerr << lCount << " " << rCount << " " << mid << endl;
// cerr << segmentTree.query(0, mid) << " " << segmentTree.query(mid+1, 1e9+7) << endl;
// cerr << endl;
ans = min(ans, L+R);
// cerr << i << " " << mid << " " << sum << endl;
sum -= A[i-K+1];
root = eraseTreap(root, Key(A[i-K+1], i-K+1));
int AA = A[i-K+1];
segmentTree.setValue(AA, segmentTree.query(AA,AA+1) - AA);
segmentTreeCount.setValue(AA, segmentTreeCount.query(AA, AA+1)-1);
}
}
cout << ans << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0