AtCoder Beginner Contest 140 E問題 - Second Sum

Source

AtCoder Beginner Contest 140
問題文

問題概要

省略

解法

省略

cLayversion 20190914-1)のコード

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

int N, P[1d5];
int inv[1d5];
{
  int i, k, lef1, lef2, rig1, rig2;
  multiset<int> s;
  multiset<int>::iterator it1, it2;
  ll res = 0;
  
  rd(N,(P--)(N));
  rep(i,N) inv[P[i]] = i;

  rep(2) s.insert(-1);
  rep(2) s.insert(N);

  for(k=N-1;k>=0;k--){
    i = inv[k];
    it1 = it2 = s.insert(i);
    lef1 = *(--it1);
    lef2 = *(--it1);
    rig1 = *(++it2);
    rig2 = *(++it2);

    res += (ll) (k+1) * (lef1-lef2) * (rig1 - i);
    res += (ll) (k+1) * (rig2-rig1) * (i - lef1);
  }

  wt(res);
}

Current time: 2021年09月18日03時37分25秒
Last modified: 2019年09月14日17時34分35秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC140 ABC_E
トップページに戻る

Logged in as: unknown user (not login)

ログイン: