Manthan, Codefest 18 (rated, Div. 1 + Div. 2)

kroton @kroton_pc

なんか他の人と方針が違うみたいだ

kroton @kroton_pc

1段目の結果は幅Kで区間maxを取ったもの、2段目の結果は幅K+(K-1)で区間maxを取ったものになるので、a[i] が K, K+(K-1), K+2(K+1)... の区間maxで何回選ばれるかを数えた。 まず自分が区間maxになれる最大の区間を探してその区間に完全に含まれていてかつ a[i] を含む区間が数えらればいい。

kroton @kroton_pc

でそういう区間の総数は Σ(ある長さの区間をa[i]を含みつつ最大限左側に寄せたときの左端とa[i]とのズレ量) + Σ(右側に〜) - Σ長さ みたいな量で計算できるのでがんばって数える。これでO(N)になった。

agw @masashinakata

@satanic0258さんと@Ymgch_Kさんに教えてもらったこどふぉのManthan D通してきた!

agw @masashinakata

ポカミスで1 WAしたんだけど、これよくないんだよなあ、と

kroton @kroton_pc

codeforces.com/contest/1037/s… 2で割る時に inverse(2) を毎回呼び出していたのを static ll inv2 = inverse(2); として1回だけにしたら3倍早くなった...