Codeforces Round #712 DIV1 D問題/DIV2 F問題 - Flip the Cards

Source

Codeforces Round #712 DIV1 D問題 (1750pt)
Codeforces Round #712 DIV2 F問題 (3000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20210404-1）のコード

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

//no-unlocked
int N, A[4d5], B[];
int sz, arr[], chk[];
int ind[], cnt1[], cnt2[];

int rv(int k){ return (k >= N) ? k - N : k + N; }

{
  unionFind uf;
  LHeap<int> hp;
  rd(N,(A--,B--)(N));

  uf.walloc(2*N, 1);
  hp.walloc(2*N);
  hp.init(2*N);

  rep(i,N) ind[i] = i;
  rep(i,N) (A[i+N], B[i+N], ind[i+N]) = (B[i], A[i], ind[i] + N);
  sortA(2*N, A, B, ind);

  rep(i,2*N){
    sz = 0;
    while(hp.size && B[hp.hp[0]] < B[i]) arr[sz++] = hp.pop();
    if(sz){
      rep(j,sz) uf(ind[arr[j]], rv(ind[i]));
      rep(j,sz) uf(rv(ind[arr[j]]), ind[i]);
      hp.change(arr[0], B[arr[0]]);
    }
    hp.change(i, B[i]);
  }
  rep(i,N) if(uf(i) == uf(i+N)) wt(-1), return 0;

  rep(i,2*N) ind[i] = -1;
  rep(i,N){
    if(chk[uf(i)] || chk[uf(i+N)]) continue;
    ind[uf(i)] = i;
    chk[uf(i)] = chk[uf(i+N)] = 1;
  }
  rep(i,2*N){
    if(ind[uf(i)] == -1) continue;
    if[i < N, cnt1, cnt2][ind[uf(i)]]++;
  }
  
  wt(sum[i,0,N](min(cnt1[i],cnt2[i])));
}

Current time: 2024年04月25日08時38分31秒
Last modified: 2021年04月04日05時16分15秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF712 CF_DIV1_D CF_DIV2_F
トップページに戻る

Logged in as: unknown user (not login)