Submission #377346
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int MOD = 1e9+7; typedef long long ll; const int INF = 1e9; template <class T> struct BIT{ int N;vector<T>bit; BIT(int n):N(n),bit(n+1){} void add(T k,int i){i++;for(int x=i;x<=N;x+=x&-x)bit[x]+=k;} T sum(int i){i++;T r=0;for(int x=i;x>0;x-=x&-x)r+=bit[x];return r;} T sum(int l,int r){return l<=r ? sum(r)-sum(l-1):sum(r)+sum(l,N-1);} T get(int i){return sum(i) - sum(i-1);} void set(T k,int i){add(k-get(i),i);} }; //座標圧縮 int compress(vector<int>& X){ vector<int> x = X; sort(x.begin(),x.end()); x.erase(unique(x.begin(),x.end()),x.end()); for(int i=0;i<X.size();i++){ X[i] = lower_bound(x.begin(),x.end(),X[i]) - x.begin(); } return x.size(); } int main(void) { int n; cin >> n; vector<int> h(n),H; vector<int> id(n); for(int i=0;i<n;i++){ cin >> h[i]; } H = h; if(n != compress(h)){ cout << -1 << endl; return 0; } BIT<int> bit(n+1); for(int i=0;i<n;i++){ bit.set(1,i); id[h[i]] = i; } ll ans = 0; for(int i=0;i<n;i++){ //cout << bit.sum(0,id[i]) << endl; ans += (ll)(bit.sum(0,id[i])-1) * H[id[i]]; bit.add(-1,id[i]); //cout << ans << endl; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Line up! |
User | tkzw_21 |
Language | C++11 (GCC 4.9.2) |
Score | 100 |
Code Size | 1279 Byte |
Status | AC |
Exec Time | 135 ms |
Memory | 2460 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 70 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt |
Subtask1 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask0_sample_01.txt, subtask0_sample_02.txt |
All | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 25 ms | 928 KB |
subtask0_sample_02.txt | AC | 26 ms | 804 KB |
subtask1_01.txt | AC | 24 ms | 924 KB |
subtask1_02.txt | AC | 26 ms | 812 KB |
subtask1_03.txt | AC | 26 ms | 800 KB |
subtask1_04.txt | AC | 26 ms | 928 KB |
subtask1_05.txt | AC | 24 ms | 796 KB |
subtask1_06.txt | AC | 26 ms | 800 KB |
subtask1_07.txt | AC | 24 ms | 808 KB |
subtask1_08.txt | AC | 25 ms | 928 KB |
subtask1_09.txt | AC | 24 ms | 928 KB |
subtask1_10.txt | AC | 24 ms | 800 KB |
subtask1_11.txt | AC | 24 ms | 800 KB |
subtask1_12.txt | AC | 26 ms | 812 KB |
subtask1_13.txt | AC | 26 ms | 928 KB |
subtask1_14.txt | AC | 26 ms | 804 KB |
subtask1_15.txt | AC | 26 ms | 804 KB |
subtask1_16.txt | AC | 26 ms | 800 KB |
subtask1_17.txt | AC | 26 ms | 924 KB |
subtask1_18.txt | AC | 26 ms | 800 KB |
subtask1_19.txt | AC | 26 ms | 816 KB |
subtask1_20.txt | AC | 26 ms | 932 KB |
subtask1_21.txt | AC | 26 ms | 804 KB |
subtask1_22.txt | AC | 26 ms | 928 KB |
subtask1_23.txt | AC | 26 ms | 808 KB |
subtask2_01.txt | AC | 104 ms | 2336 KB |
subtask2_02.txt | AC | 111 ms | 2340 KB |
subtask2_03.txt | AC | 111 ms | 2348 KB |
subtask2_04.txt | AC | 58 ms | 2332 KB |
subtask2_05.txt | AC | 123 ms | 2264 KB |
subtask2_06.txt | AC | 108 ms | 2340 KB |
subtask2_07.txt | AC | 110 ms | 2268 KB |
subtask2_08.txt | AC | 109 ms | 2344 KB |
subtask2_09.txt | AC | 110 ms | 2264 KB |
subtask2_10.txt | AC | 110 ms | 2264 KB |
subtask2_11.txt | AC | 133 ms | 2336 KB |
subtask2_12.txt | AC | 133 ms | 2336 KB |
subtask2_13.txt | AC | 132 ms | 2460 KB |
subtask2_14.txt | AC | 132 ms | 2332 KB |
subtask2_15.txt | AC | 133 ms | 2332 KB |
subtask2_16.txt | AC | 131 ms | 2328 KB |
subtask2_17.txt | AC | 133 ms | 2332 KB |
subtask2_18.txt | AC | 135 ms | 2332 KB |
subtask2_19.txt | AC | 134 ms | 2344 KB |
subtask2_20.txt | AC | 134 ms | 2332 KB |