2020年11月21日18時57分11秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．

Codeforces Round #684 DIV1 C問題/DIV2 E問題 - Greedy Shopping

Source

Codeforces Round #684 DIV1 C問題 (1750pt)
Codeforces Round #684 DIV2 E問題 (2500pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20201121-1）のコード

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日09時33分36秒
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)