結果
問題 |
No.3221 Count Turns
|
ユーザー |
![]() |
提出日時 | 2025-08-01 23:14:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,070 ms / 2,000 ms |
コード長 | 25,128 bytes |
コンパイル時間 | 3,272 ms |
コンパイル使用メモリ | 289,512 KB |
実行使用メモリ | 36,992 KB |
最終ジャッジ日時 | 2025-08-01 23:14:45 |
合計ジャッジ時間 | 21,292 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; using ull=unsigned long long; using P=pair<ll,ll>; template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>; template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);} template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;} template<typename T1,typename T2,typename T3>istream &operator>>(istream &is,tuple<T1,T2,T3>&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;} template<typename T,size_t n>istream &operator>>(istream &is,array<T,n>&a){for(auto&i:a)is>>i;return is;} template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;} template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;} template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;} template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;} template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;} #define overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast<void>(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template<typename T> inline int fkey(vector<T>&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();} ll myceil(ll a,ll b){return (a+b-1)/b;} template<typename T,size_t n,size_t id=0> auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init)); else return init; } #ifdef LOCAL #include<debug.h> #define SWITCH(a,b) (a) #else #define debug(...) static_cast<void>(0) #define debugg(...) static_cast<void>(0) #define SWITCH(a,b) (b) template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;} #endif struct Timer{ clock_t start; Timer(){ start=clock(); ios::sync_with_stdio(false); cin.tie(nullptr); cout<<fixed<<setprecision(16); } inline double now(){return (double)(clock()-start)/1000;} #ifdef LOCAL ~Timer(){ cerr<<"time:"; cerr<<now(); cerr<<"ms\n"; } #endif }timer; void SOLVE(); int main(){ int testcase=1; //cin>>testcase; for(int i=0;i<testcase;i++){ SOLVE(); } } #include<type_traits> struct has_update_impl{ template<typename T> static auto check(T&&x)->decltype(x.update(),std::true_type{}); template<typename T> static auto check(...)->std::false_type; }; template<typename T> struct has_update:public decltype(has_update_impl::check<T>(std::declval<T>())){}; template<typename T> inline constexpr bool has_update_v=has_update<T>::value; struct has_push_impl{ template<typename T> static auto check(T&&x)->decltype(x.push(),std::true_type{}); template<typename T> static auto check(...)->std::false_type; }; template<typename T> struct has_push:public decltype(has_push_impl::check<T>(std::declval<T>())){}; template<typename T> inline constexpr bool has_push_v=has_push<T>::value; struct has_middle_impl{ template<typename T> static auto check(T&&x)->decltype(x.middle,std::true_type{}); template<typename T> static auto check(...)->std::false_type; }; template<typename T> struct has_middle:public decltype(has_middle_impl::check<T>(std::declval<T>())){}; template<typename T> inline constexpr bool has_middle_v=has_middle<T>::value; template<typename T,bool no_push=false> void splay(T*nd){ if constexpr(has_push_v<T>&&!no_push)nd->push(); while(nd->par){ T *p=nd->par; T *pp=p->par; if constexpr(has_push_v<T>&&!no_push){ if(pp)pp->push(); p->push(); nd->push(); } if(p->left==nd){ if(pp){ if(pp->left==p){ nd->par=pp->par; if(pp->par){ if constexpr(has_middle_v<T>){ if(pp->par->middle==pp)nd->par->middle=nd; else if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } else{ if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } } pp->left=p->right; if(pp->left)pp->left->par=pp; p->left=nd->right; if(p->left)p->left->par=p; nd->right=p; p->par=nd; p->right=pp; pp->par=p; if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update(); continue; } else if(pp->right==p){ nd->par=pp->par; if(pp->par){ if constexpr(has_middle_v<T>){ if(pp->par->middle==pp)nd->par->middle=nd; else if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } else{ if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } } p->left=nd->right; if(p->left)p->left->par=p; pp->right=nd->left; if(pp->right)pp->right->par=pp; nd->left=pp; pp->par=nd; nd->right=p; p->par=nd; if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update(); continue; } } nd->par=pp; if(pp){ if constexpr(has_middle_v<T>){ if(pp->middle==p)pp->middle=nd; else if(pp->left==p)pp->left=nd; else if(pp->right==p)pp->right=nd; } else{ if(pp->left==p)pp->left=nd; else if(pp->right==p)pp->right=nd; } } p->left=nd->right; if(p->left)p->left->par=p; nd->right=p; p->par=nd; if constexpr(has_update_v<T>)p->update(),nd->update(); break; } else if(p->right==nd){ if(pp){ if(pp->left==p){ nd->par=pp->par; if(pp->par){ if constexpr(has_middle_v<T>){ if(pp->par->middle==pp)nd->par->middle=nd; else if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } else{ if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } } p->right=nd->left; if(p->right)p->right->par=p; pp->left=nd->right; if(pp->left)pp->left->par=pp; nd->left=p; p->par=nd; nd->right=pp; pp->par=nd; if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update(); continue; } else if(pp->right==p){ nd->par=pp->par; if(pp->par){ if constexpr(has_middle_v<T>){ if(pp->par->middle==pp)nd->par->middle=nd; else if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } else{ if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } } pp->right=p->left; if(pp->right)pp->right->par=pp; p->right=nd->left; if(p->right)p->right->par=p; nd->left=p; p->par=nd; p->left=pp; pp->par=p; if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update(); continue; } } nd->par=pp; if(pp){ if constexpr(has_middle_v<T>){ if(pp->middle==p)pp->middle=nd; else if(pp->left==p)pp->left=nd; else if(pp->right==p)pp->right=nd; } else{ if(pp->left==p)pp->left=nd; else if(pp->right==p)pp->right=nd; } } p->right=nd->left; if(p->right)p->right->par=p; nd->left=p; p->par=nd; if constexpr(has_update_v<T>)p->update(),nd->update(); break; } else break; } } template<typename T> [[nodiscard]]T* near(T *nd,decltype(T::key)k){ while(true){ if(k<nd->key){ if constexpr(has_push_v<T>)nd->push(); if(nd->left)nd=nd->left; else{ splay<T,true>(nd); return nd; } } else if(nd->key<k){ if constexpr(has_push_v<T>)nd->push(); if(nd->right)nd=nd->right; else{ splay<T,true>(nd); return nd; } } else{ splay<T,true>(nd); return nd; } } return nullptr; } template<typename T> [[nodiscard]]T* get_k(T *nd,decltype(T::sz)k){ while(true){ if constexpr(has_push_v<T>)nd->push(); decltype(T::sz) lsz=nd->left?nd->left->sz:0; if(lsz==k)break; else if(k<lsz)nd=nd->left; else{ nd=nd->right; k-=1+lsz; } } splay<T,true>(nd); return nd; } template<typename T> [[nodiscard]]T* merge(T* l,T *r){ if(!l)return r; if(!r)return l; while(r->left){ if constexpr(has_push_v<T>)r->push(); r=r->left; } if constexpr(has_push_v<T>)r->push(); splay<T,true>(r); r->left=l; l->par=r; if constexpr(has_update_v<T>)r->update(); return r; } template<typename T,bool correct_parent=true> [[nodiscard]]T* left_most(T*nd){ T nil; T *rnd=&nil; while(nd->left){ if constexpr(has_push_v<T>)nd->push(); T *c=nd->left; if(!c->left){ rnd->left=nd; if constexpr(has_update_v<T>||correct_parent)nd->par=rnd; rnd=rnd->left; nd=c; } else{ if constexpr(has_push_v<T>)c->push(); nd->left=c->right; c->right=nd; if constexpr(has_update_v<T>||correct_parent){ if(nd->left)nd->left->par=nd; nd->par=c; } if constexpr(has_update_v<T>)nd->update(); if constexpr(has_update_v<T>||correct_parent)c->par=rnd; rnd->left=c; nd=c->left; rnd=rnd->left; } } if constexpr(has_push_v<T>)nd->push(); rnd->left=nd->right; nd->right=nil.left; nil.left=nil.right=nullptr; if constexpr(has_update_v<T>||correct_parent){ if(rnd->left)rnd->left->par=rnd; if(nd->right)nd->right->par=nd; nd->par=nullptr; } if constexpr(has_update_v<T>){ while(rnd){ rnd->update(); rnd=rnd->par; } } return nd; } template<typename T,bool correct_parent=true> [[nodiscard]]T* right_most(T*nd){ T nil; T *lnd=&nil; while(nd->right){ if constexpr(has_push_v<T>)nd->push(); T *c=nd->right; if(!c->right){ lnd->right=nd; if constexpr(has_update_v<T>||correct_parent)nd->par=lnd; lnd=lnd->right; nd=c; } else{ if constexpr(has_push_v<T>)c->push(); nd->right=c->left; c->left=nd; if constexpr(has_update_v<T>||correct_parent){ if(nd->right)nd->right->par=nd; nd->par=c; } if constexpr(has_update_v<T>){ nd->update(); } if constexpr(has_update_v<T>||correct_parent)c->par=lnd; lnd->right=c; nd=c->right; lnd=lnd->right; } } if constexpr(has_push_v<T>)nd->push(); lnd->right=nd->left; nd->left=nil.right; nil.left=nil.right=nullptr; if constexpr(has_update_v<T>||correct_parent){ if(lnd->right)lnd->right->par=lnd; if(nd->left)nd->left->par=nd; nd->par=nullptr; } if constexpr(has_update_v<T>){ while(lnd){ lnd->update(); lnd=lnd->par; } } return nd; } #include<concepts> template<typename T> constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);} template<typename T> constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);} template<typename T> constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);} template<typename T> constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);} template<typename T> constexpr std::enable_if_t<std::is_integral_v<T>,T>floor_pow2(T n){return n==0?0:T(1)<<msb(n);} template<typename T> constexpr std::enable_if_t<std::is_integral_v<T>,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);} template<std::integral T> constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);} template<std::integral T> constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);} template<typename T,typename T2> struct DynamicConvexHullTrick{ static_assert(std::is_integral_v<T>); private: static constexpr T inf=std::numeric_limits<T>::max(); struct line{ T a,b; int idx; line():a(0),b(inf),idx(-1){} line(T a_,T b_,int idx_):a(a_),b(b_),idx(idx_){} inline T operator()(T x)const{ return a*x+b; } static bool convex(const line&a,const line&b,const line&c){ return safe_div(b.b-c.b,c.a-b.a)<safe_div(a.b-b.b,b.a-a.a); } }; struct splay_node{ splay_node *left,*right,*par; T b; int idx; splay_node():left(nullptr),right(nullptr),par(nullptr),b(inf),idx(-1){} explicit splay_node(T b_,int idx_):left(nullptr),right(nullptr),par(nullptr),b(b_),idx(idx_){} }; struct AVL{ struct avl_node{ avl_node *left,*right,*par; int8_t height; line lc,rc; T lm; splay_node *bs; T bmin; int bminidx; bool lazy; avl_node():left(nullptr),right(nullptr),par(nullptr),height(0),bs(nullptr),bmin(inf),bminidx(-1),lazy(false){} avl_node(T a,T b,int idx_):left(nullptr),right(nullptr),par(nullptr),height(0),lc(a,b,idx_),rc(a,b,idx_),lm(a),bs(new splay_node(b,idx_)),bmin(b),bminidx(idx_),lazy(false){} inline int8_t diff()const{ return (left?left->height:0)-(right?right->height:0); } inline void light_update(){ lm=left->lm; height=std::max(left->height,right->height)+1; } inline void heavy_update(){ if(!lazy)return; left->heavy_update(); right->heavy_update(); avl_node *lnd=left,*rnd=right; T midx=rnd->lm; while(lnd->left||rnd->left){ if(lnd->left&&rnd->left){ if(!line::convex(lnd->lc,lnd->rc,rnd->lc)){ lnd=lnd->left; } else if(!line::convex(lnd->rc,rnd->lc,rnd->rc)){ rnd=rnd->right; } else{ if((T2(lnd->rc.b-lnd->lc.b)*T2(midx-lnd->lc.a)+T2(lnd->lc.b)*T2(lnd->rc.a-lnd->lc.a))*T2(rnd->rc.a-rnd->lc.a)<(T2(rnd->rc.b-rnd->lc.b)*T2(midx-rnd->lc.a)+T2(rnd->lc.b)*T2(rnd->rc.a-rnd->lc.a))*T2(lnd->rc.a-lnd->lc.a)){ lnd=lnd->right; } else{ rnd=rnd->left; } } } else if(lnd->left){ if(line::convex(lnd->lc,lnd->rc,rnd->lc))lnd=lnd->right; else lnd=lnd->left; } else{ if(line::convex(lnd->rc,rnd->lc,rnd->rc))rnd=rnd->left; else rnd=rnd->right; } } lc=lnd->lc,rc=rnd->rc; lazy=false; } }; static avl_node* rotl(avl_node*nd){ avl_node *ch=nd->right; if(nd->par){ if(nd->par->left==nd)nd->par->left=ch; else nd->par->right=ch; } ch->par=nd->par; nd->right=ch->left; nd->right->par=nd; ch->left=nd; nd->par=ch; return ch; } static avl_node* rotr(avl_node*nd){ avl_node *ch=nd->left; if(nd->par){ if(nd->par->left==nd)nd->par->left=ch; else nd->par->right=ch; } ch->par=nd->par; nd->left=ch->right; nd->left->par=nd; ch->right=nd; nd->par=ch; return ch; } static avl_node* balance(avl_node*nd){ if(nd->diff()==2){ if(nd->left->diff()==-1){ nd->left=rotl(nd->left); nd=rotr(nd); nd->left->light_update(); nd->right->light_update(); nd->light_update(); nd->left->lazy=nd->right->lazy=nd->lazy=true; } else{ nd=rotr(nd); nd->right->light_update(); nd->light_update(); nd->right->lazy=nd->lazy=true; } } else if(nd->diff()==-2){ if(nd->right->diff()==1){ nd->right=rotr(nd->right); nd=rotl(nd); nd->left->light_update(); nd->right->light_update(); nd->light_update(); nd->left->lazy=nd->right->lazy=nd->lazy=true; } else{ nd=rotl(nd); nd->left->light_update(); nd->light_update(); nd->left->lazy=nd->lazy=true; } } else{ nd->light_update(); nd->lazy=true; } return nd; } static void insert(avl_node*&root,T a,T b,int idx){ if(!root){ root=new avl_node(a,b,idx); return; } avl_node *nd=root; while(nd->left){ if(a<nd->right->lm)nd=nd->left; else nd=nd->right; } if(nd->lm==a){ splay_node *snd=nd->bs; while(true){ if(snd->b>b||(snd->b==b&&snd->idx>idx)){ if(snd->left)snd=snd->left; else{ splay_node *nxt=new splay_node(b,idx); snd->left=nxt; nxt->par=snd; snd=nxt; splay(snd); break; } } else{ if(snd->right)snd=snd->right; else{ splay_node *nxt=new splay_node(b,idx); snd->right=nxt; nxt->par=snd; snd=nxt; splay(snd); break; } } } nd->bs=snd; if(nd->bmin<=b)return; nd->bmin=b; nd->bminidx=idx; nd->lc=nd->rc=line(nd->lm,b,idx); if(!nd->par)root=nd; else{ nd=nd->par; while(true){ nd->light_update(); nd->lazy=true; if(nd->par)nd=nd->par; else break; } root=nd; } } else{ avl_node *nch=new avl_node(a,b,idx); avl_node *np=new avl_node(); if(nd->par){ if(nd->par->left==nd)nd->par->left=np; else nd->par->right=np; np->par=nd->par; } nch->par=np; nd->par=np; if(a<nd->lm){ np->left=nch; np->right=nd; } else{ np->left=nd; np->right=nch; } while(true){ np=balance(np); if(np->par)np=np->par; else break; } root=np; } } static bool erase(avl_node*&root,T a,T b,int idx=-1){ if(!root)return false; avl_node *nd=root; while(nd->left){ if(a<nd->right->lm)nd=nd->left; else nd=nd->right; } if(nd->lm==a){ splay_node *snd=nd->bs; while(true){ if(snd->b==b&&(idx==-1||snd->idx==idx))break; else if(snd->b>b||(snd->b==b&&snd->idx>idx)){ if(snd->left)snd=snd->left; else break; } else{ if(snd->right)snd=snd->right; else break; } } splay(snd); nd->bs=snd; if(snd->b==b&&(idx==-1||snd->idx==idx)){ if(snd->left)snd->left->par=nullptr; if(snd->right)snd->right->par=nullptr; nd->bs=merge(snd->left,snd->right); delete snd; if(nd->bs){ nd->bs=left_most(nd->bs); nd->bminidx=nd->bs->idx; nd->bmin=nd->bs->b; nd->lc=nd->rc=line(nd->lm,nd->bmin,nd->bminidx); if(nd->par){ nd=nd->par; while(true){ nd->light_update(); nd->lazy=true; if(nd->par)nd=nd->par; else break; } } root=nd; } else{ if(nd->par){ avl_node*p=nd->par; if(p->par){ avl_node*nnd; if(p->left==nd)nnd=p->right; else nnd=p->left; if(p->par->left==p)p->par->left=nnd; else p->par->right=nnd; nnd->par=p->par; delete p; delete nd; nnd=nnd->par; while(true){ nnd=balance(nnd); if(nnd->par)nnd=nnd->par; else break; } root=nnd; } else{ if(p->left==nd)root=p->right; else root=p->left; root->par=nullptr; delete p; delete nd; } } else{ root=nullptr; delete nd; } } return true; } else return false; } else return false; } }; typename AVL::avl_node *root; public: DynamicConvexHullTrick():root(nullptr){} void add(T a,T b,int idx=-1){ AVL::insert(root,a,b,idx); } bool erase(T a,T b,int idx=-1){ return AVL::erase(root,a,b,idx); } line min(T x)const{ if(!root)return line(0,inf,-1); root->heavy_update(); typename AVL::avl_node *nd=root; while(nd->left){ T leval=nd->lc(x),reval=nd->rc(x); if(leval<reval)nd=nd->left; else if(leval>reval)nd=nd->right; else if(nd->lc.idx<nd->rc.idx)nd=nd->left; else nd=nd->right; } return nd->lc; } }; template<typename M> struct SegmentTree{ using S=typename M::S; private: int n,z; std::vector<S>dat; public: SegmentTree():n(0),z(0),dat(){} explicit SegmentTree(int n):n(n),z(ceil_pow2(n)),dat(ceil_pow2(n)*2,M::e()){} explicit SegmentTree(const std::vector<S>&a):n(a.size()),z(ceil_pow2((int)a.size())){ dat.resize(z*2,M::e()); for(int i=0;i<n;i++)dat[i+z]=a[i]; for(int i=z-1;i>=1;i--)dat[i]=M::op(dat[i*2],dat[i*2+1]); } SegmentTree(int n,S init):SegmentTree(std::vector<S>(n,init)){} inline S get(int i)const{return dat[i+z];} void set(int i,S x){ assert(0<=i&&i<n); i+=z; dat[i]=x; i>>=1; while(i){ dat[i]=M::op(dat[i*2],dat[i*2+1]); i>>=1; } } S prod(int l,int r)const{ assert(0<=l&&l<=r&&r<=n); l+=z,r+=z; S left=M::e(),right=M::e(); while(l<r){ if(l&1)left=M::op(left,dat[l++]); if(r&1)right=M::op(dat[--r],right); l>>=1,r>>=1; } return M::op(left,right); } inline S all_prod()const{return dat[1];} template<typename Func> int max_right(int l,const Func&f){ if(l==n)return n; l+=z; S now=M::e(); do{ while((~l)&1)l>>=1; S nxt=M::op(now,dat[l]); if(f(nxt))now=nxt,l++; else{ while(l<z){ l<<=1; nxt=M::op(now,dat[l]); if(f(nxt))now=nxt,l++; } return l-z; } }while(l!=(l&-l)); return n; } template<typename Func> int min_left(int r,const Func&f){ if(r==0)return 0; r+=z; S now=M::e(); do{ r--; while(r>1&&(r&1))r>>=1; S nxt=M::op(dat[r],now); if(f(nxt))now=nxt; else{ while(r<z){ r=(r<<1)+1; nxt=M::op(dat[r],now); if(f(nxt))now=nxt,r--; } return r-z+1; } }while(r!=(r&-r)); return 0; } friend std::ostream &operator<<(std::ostream &os,const SegmentTree&seg){ os<<"{"; for(int i=0;i<seg.n;i++)os<<seg.dat[i+seg.z]<<",}"[i+1==seg.n]; if(seg.n==0)os<<"}"; return os; } }; template<typename T,T E=std::numeric_limits<T>::max()> struct MonoidMin{ using S=T; using F=std::nullptr_t; static inline S op(const S&x,const S&y){return x<y?x:y;} static inline S e(){return E;} static inline S mapping(F,const S&x,long long){return x;} static inline F composition(F,F){return nullptr;} static inline F id(){return nullptr;} static inline void revS(S&x){} static inline S pow(const S&x,long long p){return x;} }; void SOLVE(){ int n,t; ll h; cin>>n>>h>>t; vector<ll>a(n); cin>>a; vector<ll>init(n); rep(i,n)init[i]=(h+a[i]-1)/a[i]; SegmentTree<MonoidMin<ll>>seg(init); DynamicConvexHullTrick<ll,__int128_t>cht; auto add_line=[&](int idx,ll aa,ll bb)->void { cht.add(-aa,-bb,idx); }; auto get_max_and_erase=[&](ll x)->int { auto l=cht.min(x); assert(cht.erase(l.a,l.b,l.idx)); return l.idx; }; rep(i,n){ add_line(i,a[i],0); } ll add=0; vector<int>c(n); while(t--){ // debug(lines); ll cnt=seg.all_prod()-add; int idx=get_max_and_erase(add+cnt); // debug(idx,cnt); c[idx]++; seg.set(idx,(h+a[idx]-1)/a[idx]+add+cnt); add_line(idx,a[idx],a[idx]*(-add-cnt)); add+=cnt; } rep(i,n)cout<<c[i]<<" \n"[i+1==n]; }