結果

問題 No.924 紲星
ユーザー beetbeet
提出日時 2020-03-08 19:08:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,537 bytes
コンパイル時間 2,678 ms
コンパイル使用メモリ 221,932 KB
実行使用メモリ 33,188 KB
最終ジャッジ日時 2024-11-07 11:55:38
合計ジャッジ時間 8,824 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 3 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 4 ms
5,248 KB
testcase_06 AC 4 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';


struct Mo{
  using F = function<void(int)>;
  vector<int> ls,rs,ord;
  int n,width,nl,nr,ptr;
  F expandL,expandR;
  F shrinkL,shrinkR;

  Mo(int n,int width,F expandL,F expandR,F shrinkL,F shrinkR):
    n(n),width(width),nl(0),nr(0),ptr(0),
    expandL(expandL),expandR(expandR),
    shrinkL(shrinkL),shrinkR(shrinkR){}

  Mo(int n,int width,F expand,F shrink){
    *this=Mo(n,width,expand,expand,shrink,shrink);
  }

  void add(int l,int r){
    ls.emplace_back(l);
    rs.emplace_back(r);
  }

  void build(){
    ord.resize(ls.size());
    iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),
         [&](int a,int b){
           if(ls[a]/width!=ls[b]/width) return ls[a]<ls[b];
           if(rs[a]==rs[b]) return ls[a]<ls[b];
           return bool((rs[a]<rs[b])^((ls[a]/width)&1));
         });
  }

  int process(){
    if(ptr==(int)ord.size()) return -1;
    const int idx=ord[ptr++];
    while(nl>ls[idx]) expandL(--nl);
    while(nr<rs[idx]) expandR(nr++);
    while(nl<ls[idx]) shrinkL(nl++);
    while(nr>rs[idx]) shrinkR(--nr);
    return idx;
  }
};


template<typename T>
struct AbsoluteSum{
  multiset<T> lp,rp;
  T sum;
  AbsoluteSum():sum(0){}

  T insert(T x){
    if(lp.empty()){
      lp.emplace(x);
      rp.emplace(x);
      return T(0);
    }
    auto p=interval();
    lp.emplace(x);
    rp.emplace(x);
    if(p.first<=x&&x<=p.second) return T(0);
    if(*lp.rbegin()>*rp.begin()){
      T a=*lp.rbegin();
      T b=*rp.begin();
      lp.erase(lp.find(a));
      rp.erase(rp.find(b));
      rp.emplace(a);
      lp.emplace(b);
    }
    T res=min(abs(p.first-x),abs(p.second-x));
    sum+=res;
    return res;
  }

  T erase(T x){
    assert(lp.count(x)+rp.count(x)>=2);
    if(lp.count(x)&&rp.count(x)){
      lp.erase(lp.find(x));
      rp.erase(rp.find(x));
      return T(0);
    }
    if(lp.count(x)){
      lp.erase(lp.find(x));
      lp.erase(lp.find(x));
      lp.emplace(*rp.begin());
      rp.erase(rp.begin());
    }else{
      rp.erase(rp.find(x));
      rp.erase(rp.find(x));
      rp.emplace(*lp.rbegin());
      lp.erase(--lp.end());
    }
    auto p=interval();
    if(p.first<=x&&x<=p.second) return T(0);
    T res=min(abs(p.first-x),abs(p.second-x));
    sum-=res;
    return res;
  }

  pair<T, T> interval(){
    assert(!lp.empty());
    return make_pair(*lp.rbegin(),*rp.begin());
  }

  T value(){return sum;}
};

//INSERT ABOVE HERE
using ll = long long;
const int MAX = 2e5+10;
int as[MAX],bs[MAX],idx[MAX];
ll ans[MAX];

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,q;
  cin>>n>>q;
  for(int i=0;i<n;i++) cin>>as[i];

  AbsoluteSum<ll> ab;
  auto expand=[&](int i){ab.insert(as[i]);};
  auto shrink=[&](int i){ab.erase(as[i]);};

  const int BS = 1000;
  Mo mo(n,BS,expand,shrink);

  for(int i=0;i<q;i++){
    int l,r;
    cin>>l>>r;
    l--;
    if(r-l>=2000){
      idx[mo.ls.size()]=i;
      mo.add(l,r);
    }else{
      for(int j=l;j<r;j++) bs[j]=as[j];
      nth_element(bs+l,bs+l+(r-l)/2,bs+r);
      int x=bs[l+(r-l)/2];
      ll res=0;
      for(int j=l;j<r;j++) res+=abs(x-bs[j]);
      ans[i]=res;
    }
  }
  mo.build();

  for(int i=0;i<(int)mo.ls.size();i++){
    int k=mo.process();
    ans[idx[k]]=ab.value();
  }

  for(int i=0;i<q;i++) cout<<ans[i]<<newl;
  cout<<flush;
  return 0;
}
0