AtCoder Beginner Contest 136 F問題 - Enclosed Points

Source

AtCoder Beginner Contest 136
問題文

問題概要

省略

解法

省略

cLayversion 20190822-2)のコード

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

#define MD 998244353

int N, X[2d5], Y[2d5];

int ind[2d5], val[2d5];
int cnt1[2d5], cnt2[2d5], cnt3[2d5], cnt4[2d5];

mint pw[200001];

{
  int i, k;
  mint res;
  fenwick<int> f;

  rd(N,(X,Y)(N));
  coordcomp(N, X);
  coordcomp(N, Y);

  pw[0] = 1;
  rep(i,N) pw[i+1] = 2 pw[i];

  rep(i,N) ind[i] = i, val[i] = X[i];
  sortA(N, val, ind);

  f.malloc(N);

  f.init(N);
  rep(k,N){
    i = ind[k];
    f.add(Y[i],1);
    cnt1[i] = f.get(Y[i]-1);
    cnt2[i] = f.range(Y[i]+1, N-1);
  }

  f.init(N);
  for(k=N-1;k>=0;k--){
    i = ind[k];
    f.add(Y[i],1);
    cnt3[i] = f.get(Y[i]-1);
    cnt4[i] = f.range(Y[i]+1, N-1);
  }

  res = 0;
  rep(i,N){
    res += pw[N] - 1;
    res -= pw[ cnt1[i] + cnt2[i] ];
    res -= pw[ cnt1[i] + cnt3[i] ];
    res -= pw[ cnt2[i] + cnt4[i] ];
    res -= pw[ cnt3[i] + cnt4[i] ];
    res += pw[ cnt1[i] ];
    res += pw[ cnt2[i] ];
    res += pw[ cnt3[i] ];
    res += pw[ cnt4[i] ];
  }

  wt(res);
}

Current time: 2021年09月28日22時30分28秒
Last modified: 2019年08月22日23時21分25秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC136 ABC_F
トップページに戻る

Logged in as: unknown user (not login)

ログイン: