結果
| 問題 |
No.3221 Count Turns
|
| ユーザー |
 Taiki0715
|
| 提出日時 | 2025-08-03 18:26:30 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 567 ms / 2,000 ms |
| コード長 | 13,626 bytes |
| コンパイル時間 | 3,434 ms |
| コンパイル使用メモリ | 287,032 KB |
| 実行使用メモリ | 32,256 KB |
| 最終ジャッジ日時 | 2025-08-03 18:26:47 |
| 合計ジャッジ時間 | 14,426 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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>
#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;
}
bool operator<(const line&rhs)const{
if(a==rhs.a){
if(b==rhs.b)return idx<rhs.idx;
return b<rhs.b;
}
return a<rhs.a;
}
bool operator==(const line&rhs)const{
return a==rhs.a&&b==rhs.b&&idx==rhs.idx;
}
};
static inline bool convex(const line&a,const line&b,const line&c){
T2 lhs=T2(b.a-a.a)*T2(c.b-a.b);
T2 rhs=T2(c.a-a.a)*T2(b.b-a.b);
if(lhs!=rhs)return lhs>rhs;
if(std::min(a.idx,c.idx)>b.idx)return true;
if(a.idx>b.idx&&a.a==b.a&&a.b==b.b)return true;
if(c.idx>b.idx&&b.a==c.a&&b.b==c.b)return true;
return false;
}
struct AVL{
struct avl_node{
avl_node *left,*right,*par;
int8_t height;
line lc,rc;
line lm;
bool lazy;
avl_node():left(nullptr),right(nullptr),par(nullptr),height(0),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,b,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.a;
while(lnd->left||rnd->left){
if(lnd->left&&rnd->left){
if(!convex(lnd->lc,lnd->rc,rnd->lc)){
lnd=lnd->left;
}
else if(!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(convex(lnd->lc,lnd->rc,rnd->lc))lnd=lnd->right;
else lnd=lnd->left;
}
else{
if(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;
line ins(a,b,idx);
while(nd->left){
if(ins<nd->right->lm)nd=nd->left;
else nd=nd->right;
}
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(ins<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;
line era(a,b,idx);
while(nd->left){
if(era<nd->right->lm)nd=nd->left;
else nd=nd->right;
}
if(!(era==nd->lm))return false;
avl_node *p=nd->par;
if(!p){
root=nullptr;
delete nd;
}
else 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;
}
return true;
}
};
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--){
ll cnt=seg.all_prod()-add;
int idx=get_max_and_erase(add+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];
}