結果

問題 No.924 紲星
ユーザー beetbeet
提出日時 2020-12-10 16:28:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,098 bytes
コンパイル時間 2,618 ms
コンパイル使用メモリ 220,480 KB
実行使用メモリ 31,132 KB
最終ジャッジ日時 2023-10-20 00:47:51
合計ジャッジ時間 8,909 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 19 ms
4,348 KB
testcase_04 AC 9 ms
4,348 KB
testcase_05 AC 25 ms
4,348 KB
testcase_06 AC 19 ms
4,348 KB
testcase_07 AC 6 ms
4,348 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 # 

 // verification-helper: PROBLEM https://yukicoder.me/problems/3124

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
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):
    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 and 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) and 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 and 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;}
};

#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  const char newl = '\n';

  int n,q;
  cin>>n>>q;

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

  AbsoluteSum<long long> dat;
  auto expand=[&](int i){dat.insert(as[i]);};
  auto shrink=[&](int i){dat.erase(as[i]);};
  Mo mo(n,300,expand,shrink);

  for(int i=0;i<q;i++){
    int l,r;
    cin>>l>>r;
    l--;
    mo.add(l,r);
  }
  mo.build();

  vector<long long> ans(q);
  for(int i=0;i<q;i++){
    int k=mo.process();
    ans[k]=dat.value();
  }

  for(auto a:ans) cout<<a<<newl;
  return 0;
}
0