Educational Codeforces Round 101 F問題 - Power Sockets

Source

Educational Codeforces Round 101 F問題
Problem description

問題概要

省略

解法

省略

cLay（version 20201229-1）のコード

C++に変換後のコードはこちら

//no-unlocked
struct sval{ll sm, sz;};

sval segtree_rh_merge(sval a, sval b){ return {a.sm+b.sm, a.sz+b.sz}; }
sval segtree_rh_apply(ll f, sval a){ return {a.sm+f*a.sz, a.sz}; }
ll segtree_rh_compose(ll f, ll g){ return f + g; }

int N; ll K, L[2d5];
segtree_rh<sval, ll> t;

bool f(sval a){ return a.sm < K; }

{
  int st = 0, res = int_inf;
  rd(N,K,L(N));
  rsortA(N, L);

  t.walloc(1d6);
  t.setN(1d6);
  rep(i,1d6) t[i] = {0, 1};
  t[0] = {1, 1};
  t[1d6-1] = {ll_inf, 1};
  t.build();

  rep(i,N){
    while(t.get(st,st+1).sm==0) st++;
    t.change(st, st+1, -1);
    t.change(st+2, st+2+(L[i]-1)/2, 1);
    t.change(st+2, st+2+L[i]/2, 1);
    res <?= t.max_right<f>(0);
  }

  wt(if[res >= 1d6-1, -1, res]);
}

Current time: 2024年04月23日18時48分02秒
Last modified: 2020年12月29日16時15分40秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces
トップページに戻る

Logged in as: unknown user (not login)