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 |
|
|
|
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 |