Codeforces Round #672 DIV2 C2問題 - Pokémon Army (hard version)

Source

Codeforces Round #672 DIV2 C2問題 (1250pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20201018-1)のコード

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

//no-unlocked
struct hoge { ll pp, pm, mp, mm; };

hoge segtree_ph_func(hoge &a, hoge &b){
  hoge res;
  res.pp = max(a.pp + b.pp, a.pm + b.mp);
  res.pm = max(a.pp + b.pm, a.pm + b.mm);
  res.mp = max(a.mp + b.pp, a.mm + b.mp);
  res.mm = max(a.mp + b.pm, a.mm + b.mm);
  return res;
}

int N, Q, A[3d5], L, R;
segtree_ph<hoge> t;
{
  ll res;
  hoge tmp;
  t.malloc(3d5);
  REP(rd_int()){
    rd(N,Q,A(N));
    t.setN(N);
    rep(i,N){
      t[i].pp = t[i].mm = 0;
      t[i].pm = A[i]; t[i].mp = -A[i];
    }
    t.build();
    res = t.get(0,N).pm;
    wt(res);
    rep(Q){
      rd(L--, R--);
      if(A[L] != A[R]){
        swap(A[L], A[R]);
        tmp.pp = tmp.mm = 0;
        tmp.pm = A[L]; tmp.mp = -A[L];
        t.change(L, tmp);
        tmp.pm = A[R]; tmp.mp = -A[R];
        t.change(R, tmp);
        res = t.get(0,N).pm;
      }
      wt(res);
    }
  }
}

cLayversion 20200920-1)のコード

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

//no-unlocked
struct hoge { ll pp, pm, mp, mm; };

void segtree_pg_func(hoge &res, hoge a, hoge b){
  res.pp = max(a.pp + b.pp, a.pm + b.mp);
  res.pm = max(a.pp + b.pm, a.pm + b.mm);
  res.mp = max(a.mp + b.pp, a.mm + b.mp);
  res.mm = max(a.mp + b.pm, a.mm + b.mm);
}

int N, Q, A[3d5], L, R;
segtree_pg<hoge> t;
{
  ll res;
  hoge tmp;
  t.malloc(3d5);
  REP(rd_int()){
    rd(N,Q,A(N));
    t.setN(N);
    rep(i,N){
      t[i].pp = t[i].mm = 0;
      t[i].pm = A[i]; t[i].mp = -A[i];
    }
    t.build();
    res = t.get(0,N).pm;
    wt(res);
    rep(Q){
      rd(L--, R--);
      if(A[L] != A[R]){
        swap(A[L], A[R]);
        tmp.pp = tmp.mm = 0;
        tmp.pm = A[L]; tmp.mp = -A[L];
        t.change(L, tmp);
        tmp.pm = A[R]; tmp.mp = -A[R];
        t.change(R, tmp);
        res = t.get(0,N).pm;
      }
      wt(res);
    }
  }
}

Current time: 2021年06月22日11時06分15秒
Last modified: 2020年10月18日05時42分43秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF672 CF_Div2_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン: