Submission #7576185


Source Code Expand

Copy
#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  ll N;
  cin >> N;
  vector<ll> t(N+1); // t[val] = index
  rep(i, N) {
    ll x;
    cin >> x;
    t[x] = i+1;
  }

  ll ans = 0;
  set<ll> s;
  for (ll val=N; val>=1; val--) {
    {
      // 右側に最大値がある場合
      ll j, i1, i2;
      auto it = s.lower_bound(t[val]);
      if (it == s.end())
        goto END1;
      i1 = *it;
      it++;
      if (it == s.end())
        i2 = N+1;
      else
        i2 = *it;

      it = s.lower_bound(t[val]);
      if (it == s.begin()) {
        j = 0;
      } else {
        it--;
        j = *it;
      }

      // printf("right %d %dx%d\n", val, (t[val]-j) , (i2-i1));
      ans += val * (t[val]-j) * (i2-i1);
      END1: ;
    }

    {
      // 左側に最大値がある場合
      ll j2, j1, i;
      auto it = s.lower_bound(t[val]);
      if (it == s.begin()) {
        goto END2;
      }
      it--;
      j1 = *it;
      if (it == s.begin()) {
        j2 = 0;
      } else {
        it--;
        j2 = *it;
      }
      it = s.lower_bound(t[val]);
      if (it == s.end()) {
        i = N+1;
      } else {
        i = *it;
      }
      // printf("left %dx%d\n", val, (j1-j2), (i-t[val]));
      ans += val * (j1-j2) * (i-t[val]);

      END2: ;
    }

    s.insert(t[val]);
  } 
  cout << ans << endl;
  return 0;
}

Submission Info

Submission Time
Task E - Second Sum
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1606 Byte
Status
Exec Time 97 ms
Memory 5760 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 500 / 500 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-small-01.txt, 01-small-02.txt, 01-small-03.txt, 01-small-04.txt, 01-small-05.txt, 02-large-01.txt, 02-large-02.txt, 02-large-03.txt, 02-large-04.txt, 02-large-05.txt, 03-max-01.txt, 03-max-02.txt, 04-min-01.txt, 05-sorted-01.txt, 05-sorted-02.txt, 06-almost-sorted-01.txt, 06-almost-sorted-02.txt, 06-almost-sorted-03.txt, 06-almost-sorted-04.txt
Case Name Status Exec Time Memory
00-sample-01.txt 1 ms 256 KB
00-sample-02.txt 1 ms 256 KB
00-sample-03.txt 1 ms 256 KB
01-small-01.txt 1 ms 256 KB
01-small-02.txt 1 ms 256 KB
01-small-03.txt 1 ms 256 KB
01-small-04.txt 1 ms 256 KB
01-small-05.txt 1 ms 256 KB
02-large-01.txt 84 ms 5120 KB
02-large-02.txt 51 ms 3328 KB
02-large-03.txt 88 ms 5248 KB
02-large-04.txt 90 ms 5376 KB
02-large-05.txt 54 ms 3456 KB
03-max-01.txt 97 ms 5760 KB
03-max-02.txt 97 ms 5760 KB
04-min-01.txt 1 ms 256 KB
05-sorted-01.txt 92 ms 5504 KB
05-sorted-02.txt 94 ms 5632 KB
06-almost-sorted-01.txt 91 ms 5248 KB
06-almost-sorted-02.txt 84 ms 5248 KB
06-almost-sorted-03.txt 94 ms 5504 KB
06-almost-sorted-04.txt 85 ms 5248 KB