結果
問題 | No.1270 Range Arrange Query |
ユーザー | beet |
提出日時 | 2020-10-23 23:11:04 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,662 ms / 7,000 ms |
コード長 | 5,974 bytes |
コンパイル時間 | 2,699 ms |
コンパイル使用メモリ | 218,016 KB |
実行使用メモリ | 5,836 KB |
最終ジャッジ日時 | 2023-09-28 17:54:22 |
合計ジャッジ時間 | 11,766 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 123 ms
4,376 KB |
testcase_07 | AC | 929 ms
4,772 KB |
testcase_08 | AC | 202 ms
4,376 KB |
testcase_09 | AC | 648 ms
4,616 KB |
testcase_10 | AC | 770 ms
4,672 KB |
testcase_11 | AC | 1,649 ms
5,660 KB |
testcase_12 | AC | 1,653 ms
5,828 KB |
testcase_13 | AC | 1,662 ms
5,692 KB |
testcase_14 | AC | 31 ms
5,836 KB |
testcase_15 | AC | 63 ms
5,828 KB |
testcase_16 | AC | 70 ms
5,664 KB |
testcase_17 | AC | 77 ms
5,832 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using Int = long long; const char newl = '\n'; 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;} template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);} template<typename T=Int> vector<T> read(size_t n){ vector<T> ts(n); for(size_t i=0;i<n;i++) cin>>ts[i]; return ts; } 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,typename E> struct SegmentTree{ using F = function<T(T,T)>; using G = function<T(T,E)>; using H = function<E(E,E)>; Int n,height; F f; G g; H h; T ti; E ei; vector<T> dat; vector<E> laz; SegmentTree(F f,G g,H h,T ti,E ei): f(f),g(g),h(h),ti(ti),ei(ei){} void init(Int n_){ n=1;height=0; while(n<n_) n<<=1,height++; dat.assign(2*n,ti); laz.assign(2*n,ei); } void build(const vector<T> &v){ Int n_=v.size(); init(n_); for(Int i=0;i<n_;i++) dat[n+i]=v[i]; for(Int i=n-1;i;i--) dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]); } inline T reflect(Int k){ return laz[k]==ei?dat[k]:g(dat[k],laz[k]); } inline void propagate(Int k){ if(laz[k]==ei) return; laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]); laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]); dat[k]=reflect(k); laz[k]=ei; } inline void thrust(Int k){ for(Int i=height;i;i--) propagate(k>>i); } inline void recalc(Int k){ while(k>>=1) dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1)); } void update(Int a,Int b,E x){ if(a>=b) return; thrust(a+=n); thrust(b+=n-1); for(Int l=a,r=b+1;l<r;l>>=1,r>>=1){ if(l&1) laz[l]=h(laz[l],x),l++; if(r&1) --r,laz[r]=h(laz[r],x); } recalc(a); recalc(b); } void set_val(Int a,T x){ thrust(a+=n); dat[a]=x;laz[a]=ei; recalc(a); } T query(Int a,Int b){ if(a>=b) return ti; thrust(a+=n); thrust(b+=n-1); T vl=ti,vr=ti; for(Int l=a,r=b+1;l<r;l>>=1,r>>=1) { if(l&1) vl=f(vl,reflect(l++)); if(r&1) vr=f(reflect(--r),vr); } return f(vl,vr); } template<typename C> Int find(Int st,C &check,T &acc,Int k,Int l,Int r){ if(l+1==r){ acc=f(acc,reflect(k)); return check(acc)?k-n:-1; } propagate(k); Int m=(l+r)>>1; if(m<=st) return find(st,check,acc,(k<<1)|1,m,r); if(st<=l&&!check(f(acc,dat[k]))){ acc=f(acc,dat[k]); return -1; } Int vl=find(st,check,acc,(k<<1)|0,l,m); if(~vl) return vl; return find(st,check,acc,(k<<1)|1,m,r); } template<typename C> Int find(Int st,C &check){ T acc=ti; return find(st,check,acc,1,0,n); } }; template<typename T> class BIT{ private: // \sum_{j < i} v[j] T sum(Int i){ T s(0); for(Int x=i;x>0;x-=(x&-x)) s+=bit[x]; return s; } public: Int n; vector<T> bit; BIT(Int n_):n(n_+1),bit(n+1,0){} // v[i] += a void add(Int i,T a){ for(Int x=++i;x<=n;x+=(x&-x)) bit[x]+=a; } // \sum_{l <= i < r} v[i] T query(Int l,Int r){return sum(r)-sum(l);} // min({x | sum(x) >= w}) Int lower_bound(const T w){ if(w<=0) return 0; T r=w; Int x=0,p=1; while(p<n) p<<=1; for(Int k=p;k>0;k>>=1){ if(x+k<=n&&bit[x+k]<r){ r-=bit[x+k]; x+=k; } } x++; assert(sum(x-1)<w and sum(x)>=w); return x; } // min({x | sum(x) > w}) Int upper_bound(T w){return lower_bound(w+1);} }; //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); Int n,q; cin>>n>>q; auto as=read(n); auto f=[&](Int a,Int b){return min(a,b);}; auto g=[&](Int a,Int b){return a+b;}; Int ti(1e9),ei(0); SegmentTree<Int, Int> seg(f,g,g,ti,ei); seg.build(vector<Int>(n+2,0)); BIT<Int> bitL(n+2),bitR(n+2); Int res=0; auto expandL=[&](Int i){ res-=bitL.query(as[i]+1,n+2); res-=bitR.query(0,as[i]); bitL.add(as[i],-1); seg.update(0,as[i],-1); }; auto expandR=[&](Int i){ res-=bitL.query(as[i]+1,n+2); res-=bitR.query(0,as[i]); bitR.add(as[i],-1); seg.update(as[i]+1,n+2,-1); }; auto shrinkL=[&](Int i){ res+=bitL.query(as[i]+1,n+2); res+=bitR.query(0,as[i]); bitL.add(as[i],+1); seg.update(0,as[i],+1); }; auto shrinkR=[&](Int i){ res+=bitL.query(as[i]+1,n+2); res+=bitR.query(0,as[i]); bitR.add(as[i],+1); seg.update(as[i]+1,n+2,+1); }; for(Int i=n-1;i>=0;i--){ res+=bitR.query(0,as[i]); bitR.add(as[i],+1); seg.update(as[i]+1,n+2,+1); } Mo mo(n,200,expandL,expandR,shrinkL,shrinkR); vector<Int> ls,rs; for(Int i=0;i<q;i++){ Int l,r; cin>>l>>r; l--; ls.emplace_back(l); rs.emplace_back(r); mo.add(l,r); } mo.build(); vector<Int> ans(q,0); for(Int i=0;i<q;i++){ Int k=mo.process(); ans[k]=(rs[k]-ls[k])*seg.query(0,n+2)+res; } for(Int i=0;i<q;i++) cout<<ans[i]<<newl; return 0; }