Codeforces Round #684 DIV1 C問題 (1750pt)
Codeforces Round #684 DIV2 E問題 (2500pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, Q, T, X, Y, A[2d5];
struct sval{ int sz; ll sm, mn; };
sval segtree_rh_merge(sval a, sval b){ return {a.sz+b.sz, a.sm+b.sm, min(a.mn, b.mn)}; }
sval segtree_rh_apply(ll f, sval a){ return {a.sz, a.sz * f, f}; }
ll segtree_rh_compose(ll f, ll g){ return f; }
bool search_min(sval a){ return a.mn > Y; }
bool search_sum(sval a){ return a.sm <= Y; }
segtree_rh<sval, ll> t;
{
int i;
rd(N,Q,A(N));
t.walloc(N);
t.setN(N);
rep(i,N) t[i] = {1, A[i], A[i]};
t.build();
rep(Q){
rd(T, X--, Y);
if(T==1){
i = t.max_right<search_min>(0,X+1);
if(i < X+1) t.change(i,X+1,Y);
}
if(T==2){
int res = 0;
while(X < N){
i = t.max_right<search_sum>(X);
if(X < i) Y -= t.get(X,i).sm;
res += i - X;
X = t.max_right<search_min>(i);
}
wt(res);
}
}
}
Current time: 2024年04月25日18時37分09秒
Last modified: 2020年11月21日18時57分11秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF684 CF_DIV1_C CF_DIV2_E
トップページに戻る
Logged in as: unknown user (not login)