Submission #2825490
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:50:10+0900
Task
B - Increment and Swap
User
Richard_for_OI
Language
C++14 (GCC 5.4.1)
Score
1500
Code Size
1464 Byte
Status
AC
Exec Time
147 ms
Memory
7808 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
1500 / 1500
Status
Set Name
Test Cases
Sample
example0.txt, example1.txt
All
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, 063.txt, example0.txt, example1.txt
Case Name
Status
Exec Time
Memory
000.txt
AC
127 ms
6784 KB
001.txt
AC
128 ms
6912 KB
002.txt
AC
129 ms
6784 KB
003.txt
AC
130 ms
6912 KB
004.txt
AC
131 ms
6784 KB
005.txt
AC
133 ms
6912 KB
006.txt
AC
134 ms
6784 KB
007.txt
AC
135 ms
6912 KB
008.txt
AC
135 ms
6912 KB
009.txt
AC
136 ms
6912 KB
010.txt
AC
136 ms
6912 KB
011.txt
AC
138 ms
7808 KB
012.txt
AC
138 ms
7808 KB
013.txt
AC
139 ms
7808 KB
014.txt
AC
139 ms
7808 KB
015.txt
AC
140 ms
7808 KB
016.txt
AC
140 ms
7808 KB
017.txt
AC
141 ms
7808 KB
018.txt
AC
141 ms
7808 KB
019.txt
AC
141 ms
7808 KB
020.txt
AC
141 ms
7808 KB
021.txt
AC
13 ms
3200 KB
022.txt
AC
121 ms
6784 KB
023.txt
AC
58 ms
3840 KB
024.txt
AC
22 ms
3456 KB
025.txt
AC
76 ms
3968 KB
026.txt
AC
15 ms
3200 KB
027.txt
AC
98 ms
6656 KB
028.txt
AC
48 ms
3840 KB
029.txt
AC
46 ms
3840 KB
030.txt
AC
47 ms
3840 KB
031.txt
AC
100 ms
6656 KB
032.txt
AC
62 ms
3840 KB
033.txt
AC
63 ms
6400 KB
034.txt
AC
109 ms
6656 KB
035.txt
AC
19 ms
3328 KB
036.txt
AC
123 ms
7808 KB
037.txt
AC
94 ms
6656 KB
038.txt
AC
24 ms
3456 KB
039.txt
AC
71 ms
6528 KB
040.txt
AC
63 ms
6400 KB
041.txt
AC
123 ms
7808 KB
042.txt
AC
99 ms
7808 KB
043.txt
AC
99 ms
7808 KB
044.txt
AC
144 ms
7808 KB
045.txt
AC
1 ms
2944 KB
046.txt
AC
33 ms
3712 KB
047.txt
AC
147 ms
7808 KB
048.txt
AC
27 ms
3840 KB
049.txt
AC
32 ms
3840 KB
050.txt
AC
43 ms
3712 KB
051.txt
AC
63 ms
3712 KB
052.txt
AC
88 ms
3840 KB
053.txt
AC
112 ms
3968 KB
054.txt
AC
138 ms
6784 KB
055.txt
AC
24 ms
3712 KB
056.txt
AC
29 ms
3840 KB
057.txt
AC
41 ms
3712 KB
058.txt
AC
59 ms
3840 KB
059.txt
AC
85 ms
3840 KB
060.txt
AC
108 ms
3968 KB
061.txt
AC
133 ms
6784 KB
062.txt
AC
93 ms
6784 KB
063.txt
AC
92 ms
6784 KB
example0.txt
AC
1 ms
2944 KB
example1.txt
AC
1 ms
2944 KB