Submission #307207


Source Code Expand

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

int b[100020], n;


struct Bit {
  const int N;
  vector<int> data;
  Bit(const int size) : N(size + 2), data(n + 4) {}
  void add(int idx, int value) {
    for (int x = idx; x <= N; x += x & -x)
      data[x] += value;
  }
  int sum(int idx) {
    int ret = 0;
    for (int x = idx; x > 0; x -= x & -x)
      ret += data[x];
    return ret;
  }
};

typedef long long ll;

typedef pair<int,int> P;

ll solve() {
  ll ans = 0;
  Bit bit(n);

  vector<P> vp;
  for(int i = 0; i < n; i++)
  {
    vp.push_back(P(b[i], i+1));
  }

  sort(vp.begin(), vp.end(), greater<P>());

  for(int i = 0; i < n; i++)
  {
    int idx = vp[i].second;

    int lhs = bit.sum(idx);
    int rhs = bit.sum(n) - lhs;

    //printf("curr:%d, lhs:%d, rhs:%d\n", idx, lhs, rhs);

    ans += min(lhs, rhs);

    //printf("curr: %d, val: %d\n", idx, bit.sum(idx));
    //ans += bit.sum(idx);
    bit.add(idx, 1);
    //printf("hage -e\n");
  }

  return ans;
}

int main() {
  while (cin >> n) {
    for(size_t i = 0; i < n; i++)
    {
      cin >> b[i];
    }
    printf("%lld\n", solve());
  }

  return 0;
}

Submission Info

Submission Time
Task C - 積み木
User brly
Language C++ (G++ 4.6.4)
Score 100
Code Size 1654 Byte
Status AC
Exec Time 90 ms
Memory 2724 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 3
AC × 33
AC × 68
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
Subtask1 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 10_small_00.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 10_small_11.txt, 10_small_12.txt, 10_small_13.txt, 10_small_14.txt, 10_small_15.txt, 10_small_16.txt, 10_small_17.txt, 10_small_18.txt, 10_small_19.txt, 10_small_20.txt, 10_small_21.txt, 10_small_22.txt, 10_small_23.txt, 10_small_24.txt, 10_small_25.txt, 10_small_26.txt, 10_small_27.txt, 10_small_28.txt, 10_small_29.txt
Subtask2 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 10_small_00.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 10_small_11.txt, 10_small_12.txt, 10_small_13.txt, 10_small_14.txt, 10_small_15.txt, 10_small_16.txt, 10_small_17.txt, 10_small_18.txt, 10_small_19.txt, 10_small_20.txt, 10_small_21.txt, 10_small_22.txt, 10_small_23.txt, 10_small_24.txt, 10_small_25.txt, 10_small_26.txt, 10_small_27.txt, 10_small_28.txt, 10_small_29.txt, 20_rand_00.txt, 20_rand_01.txt, 20_rand_02.txt, 20_rand_03.txt, 20_rand_04.txt, 20_rand_05.txt, 20_rand_06.txt, 20_rand_07.txt, 20_rand_08.txt, 20_rand_09.txt, 20_rand_10.txt, 20_rand_11.txt, 20_rand_12.txt, 20_rand_13.txt, 20_rand_14.txt, 20_rand_15.txt, 20_rand_16.txt, 20_rand_17.txt, 20_rand_18.txt, 20_rand_19.txt, 20_rand_20.txt, 20_rand_21.txt, 20_rand_22.txt, 20_rand_23.txt, 20_rand_24.txt, 20_rand_25.txt, 20_rand_26.txt, 20_rand_27.txt, 20_rand_28.txt, 20_rand_29.txt, 30_max_0.txt, 30_max_1.txt, 30_max_2.txt, 30_max_3.txt, 30_max_4.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 21 ms 804 KB
00_sample_01.txt AC 21 ms 676 KB
00_sample_02.txt AC 20 ms 924 KB
10_small_00.txt AC 22 ms 800 KB
10_small_01.txt AC 23 ms 916 KB
10_small_02.txt AC 21 ms 900 KB
10_small_03.txt AC 23 ms 728 KB
10_small_04.txt AC 21 ms 916 KB
10_small_05.txt AC 21 ms 804 KB
10_small_06.txt AC 22 ms 800 KB
10_small_07.txt AC 23 ms 796 KB
10_small_08.txt AC 22 ms 804 KB
10_small_09.txt AC 21 ms 800 KB
10_small_10.txt AC 22 ms 808 KB
10_small_11.txt AC 23 ms 924 KB
10_small_12.txt AC 22 ms 796 KB
10_small_13.txt AC 22 ms 804 KB
10_small_14.txt AC 22 ms 800 KB
10_small_15.txt AC 21 ms 800 KB
10_small_16.txt AC 22 ms 792 KB
10_small_17.txt AC 22 ms 800 KB
10_small_18.txt AC 22 ms 796 KB
10_small_19.txt AC 23 ms 804 KB
10_small_20.txt AC 22 ms 928 KB
10_small_21.txt AC 22 ms 804 KB
10_small_22.txt AC 23 ms 804 KB
10_small_23.txt AC 21 ms 800 KB
10_small_24.txt AC 23 ms 800 KB
10_small_25.txt AC 22 ms 800 KB
10_small_26.txt AC 23 ms 672 KB
10_small_27.txt AC 20 ms 672 KB
10_small_28.txt AC 23 ms 796 KB
10_small_29.txt AC 21 ms 676 KB
20_rand_00.txt AC 62 ms 1828 KB
20_rand_01.txt AC 25 ms 928 KB
20_rand_02.txt AC 32 ms 1304 KB
20_rand_03.txt AC 42 ms 1320 KB
20_rand_04.txt AC 67 ms 2388 KB
20_rand_05.txt AC 80 ms 2580 KB
20_rand_06.txt AC 85 ms 2592 KB
20_rand_07.txt AC 67 ms 2460 KB
20_rand_08.txt AC 33 ms 1320 KB
20_rand_09.txt AC 30 ms 1068 KB
20_rand_10.txt AC 62 ms 1828 KB
20_rand_11.txt AC 41 ms 1392 KB
20_rand_12.txt AC 39 ms 1396 KB
20_rand_13.txt AC 48 ms 1704 KB
20_rand_14.txt AC 38 ms 1316 KB
20_rand_15.txt AC 24 ms 1056 KB
20_rand_16.txt AC 49 ms 1696 KB
20_rand_17.txt AC 25 ms 804 KB
20_rand_18.txt AC 87 ms 2712 KB
20_rand_19.txt AC 33 ms 1320 KB
20_rand_20.txt AC 30 ms 1060 KB
20_rand_21.txt AC 61 ms 1824 KB
20_rand_22.txt AC 63 ms 1944 KB
20_rand_23.txt AC 87 ms 2592 KB
20_rand_24.txt AC 50 ms 1708 KB
20_rand_25.txt AC 52 ms 1696 KB
20_rand_26.txt AC 44 ms 1704 KB
20_rand_27.txt AC 47 ms 1824 KB
20_rand_28.txt AC 75 ms 2460 KB
20_rand_29.txt AC 29 ms 1056 KB
30_max_0.txt AC 90 ms 2720 KB
30_max_1.txt AC 89 ms 2716 KB
30_max_2.txt AC 89 ms 2724 KB
30_max_3.txt AC 89 ms 2644 KB
30_max_4.txt AC 87 ms 2716 KB