Submission #2825482
Source Code Expand
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[200010], b[200010];
int n, bs;
int mn[800010], tag[800010];
void build(int p, int l, int r) {
if(l == r) {
mn[p] = b[l]; tag[p] = 0;
return ;
}
int mid = (l + r)>>1;
build(p<<1, l, mid); build(p<<1|1, mid + 1, r);
mn[p] = min(mn[p<<1], mn[p<<1|1]);
}
inline void pd(int p) {
tag[p<<1]+= tag[p]; mn[p<<1]+= tag[p];
tag[p<<1|1]+= tag[p]; mn[p<<1|1]+= tag[p];
tag[p] = 0;
}
void add(int p, int l, int r, int x, int y) {
if(x > y) return ;
if(x <= l && r <= y) {
++tag[p];
++mn[p];
return ;
}
int mid = (l + r)>>1;
pd(p);
if(x <= mid) add(p<<1, l, mid, x, y);
if(mid + 1 <= y) add(p<<1|1, mid + 1, r, x, y);
mn[p] = min(mn[p<<1], mn[p<<1|1]);
}
int query(int p, int l, int r, int x, int y) {
if(x <= l && r <= y) return mn[p];
int mid = (l + r)>>1;
int s1 = 0x7fffffff, s2 = 0x7fffffff;
pd(p);
if(x <= mid) s1 = query(p<<1, l, mid, x, y);
if(mid + 1 <= y) s2 = query(p<<1|1, mid + 1, r, x, y);
return min(s1, s2);
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
memcpy(b, a, sizeof(b)); sort(b+1, b+n+1); bs = unique(b+1, b+n+1) - b - 1;
build(1, 1, bs);
long long ans = 0;
for(int i = 1; i <= n; ++i) {
int p = lower_bound(b+1, b+bs+1, a[i]) - b;
ans+= query(1, 1, bs, p, bs) - a[i];
add(1, 1, bs, 1, p - 1);
}
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time
2018-07-11 17:49:01+0900
Task
A - Awkward
User
Richard_for_OI
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1464 Byte
Status
WA
Exec Time
2 ms
Memory
3072 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:45:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:46:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 1000
Status
Set Name
Test Cases
Sample
a01, a02, a03, a04
All
a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46, b47, b48, b49, b50, b51, b52, b53, b54, b55
Case Name
Status
Exec Time
Memory
a01
WA
1 ms
2944 KB
a02
WA
1 ms
2944 KB
a03
WA
1 ms
2944 KB
a04
WA
1 ms
2944 KB
b05
WA
1 ms
2944 KB
b06
WA
2 ms
2944 KB
b07
WA
2 ms
3072 KB
b08
WA
2 ms
2944 KB
b09
WA
2 ms
2944 KB
b10
WA
2 ms
2944 KB
b11
WA
2 ms
2944 KB
b12
WA
2 ms
2944 KB
b13
WA
2 ms
2944 KB
b14
WA
2 ms
2944 KB
b15
WA
2 ms
2944 KB
b16
WA
2 ms
2944 KB
b17
WA
1 ms
2944 KB
b18
WA
1 ms
2944 KB
b19
WA
2 ms
3072 KB
b20
WA
2 ms
2944 KB
b21
WA
2 ms
2944 KB
b22
WA
2 ms
2944 KB
b23
WA
2 ms
3072 KB
b24
WA
2 ms
2944 KB
b25
WA
2 ms
2944 KB
b26
WA
2 ms
2944 KB
b27
WA
2 ms
3072 KB
b28
WA
2 ms
2944 KB
b29
WA
2 ms
3072 KB
b30
WA
2 ms
3072 KB
b31
WA
2 ms
3072 KB
b32
WA
2 ms
3072 KB
b33
WA
2 ms
3072 KB
b34
WA
2 ms
3072 KB
b35
WA
2 ms
3072 KB
b36
WA
2 ms
2944 KB
b37
WA
2 ms
2944 KB
b38
WA
2 ms
3072 KB
b39
WA
2 ms
3072 KB
b40
WA
2 ms
3072 KB
b41
WA
2 ms
3072 KB
b42
WA
2 ms
3072 KB
b43
WA
2 ms
2944 KB
b44
WA
2 ms
2944 KB
b45
WA
2 ms
3072 KB
b46
WA
2 ms
3072 KB
b47
WA
2 ms
3072 KB
b48
WA
2 ms
3072 KB
b49
WA
2 ms
3072 KB
b50
WA
2 ms
2944 KB
b51
WA
2 ms
2944 KB
b52
WA
2 ms
2944 KB
b53
WA
2 ms
2944 KB
b54
WA
2 ms
2944 KB
b55
WA
2 ms
2944 KB