AtCoder Beginner Contest 136
問題文
省略
省略
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: 2024年03月28日20時47分37秒
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)