Submission #1816570
Source Code Expand
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#define pb push_back
#define mp make_pair
using namespace std;
template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }
typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;
const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1e18;
const int N=1e6;
int gi() {
int w=0;bool q=1;char c=getchar();
while ((c<'0'||c>'9') && c!='-') c=getchar();
if (c=='-') q=0,c=getchar();
while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
return q? w:-w;
}
#define lc (i<<1)
#define rc (lc|1)
int tag[N];PR mi[N];
int a[N],b[N];
inline void build(int i,int l,int r) {
mi[i]=mp(b[l],l);
if (l!=r) {
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
}
inline void pushdown(int i) {
if (tag[i]) {
mi[lc].first+=tag[i],mi[rc].first+=tag[i];
tag[lc]+=tag[i],tag[rc]+=tag[i];
tag[i]=0;
}
}
inline void modify(int i,int l,int r,int L,int R) {
if (L<=l&&r<=R) tag[i]++,mi[i].first++;
else {
int mid=(l+r)>>1;
pushdown(i);
if (L<=mid) modify(lc,l,mid,L,R);
if (mid<R) modify(rc,mid+1,r,L,R);
mi[i]=min(mi[lc],mi[rc]);
}
}
inline PR query(int i,int l,int r,int L,int R) {
if (L<=l&&r<=R) return mi[i];
int mid=(l+r)>>1;PR ans=mp(oo,0);
pushdown(i);
if (L<=mid) upmin(ans,query(lc,l,mid,L,R));
if (mid<R) upmin(ans,query(rc,mid+1,r,L,R));
return ans;
}
int main()
{
int n=gi(),i,len,k;PR p;LL ans=0;
for (i=1;i<=n;i++) a[i]=b[i]=gi();
sort(b+1,b+1+n);
len=unique(b+1,b+1+n)-b-1;
build(1,1,len);
for (i=1;i<=n;i++) {
k=lower_bound(b+1,b+len+1,a[i])-b;
p=query(1,1,len,k,len);
ans+=p.first-a[i];
if (p.second!=1)
modify(1,1,len,1,p.second-1);
}
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Increment and Swap |
User |
laofu |
Language |
C++14 (GCC 5.4.1) |
Score |
1500 |
Code Size |
2124 Byte |
Status |
AC |
Exec Time |
160 ms |
Memory |
15360 KB |
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 |
135 ms |
13312 KB |
001.txt |
AC |
134 ms |
13312 KB |
002.txt |
AC |
136 ms |
13312 KB |
003.txt |
AC |
138 ms |
13312 KB |
004.txt |
AC |
138 ms |
13312 KB |
005.txt |
AC |
137 ms |
13312 KB |
006.txt |
AC |
136 ms |
13312 KB |
007.txt |
AC |
145 ms |
13312 KB |
008.txt |
AC |
142 ms |
13312 KB |
009.txt |
AC |
143 ms |
13312 KB |
010.txt |
AC |
141 ms |
13312 KB |
011.txt |
AC |
142 ms |
15360 KB |
012.txt |
AC |
142 ms |
15360 KB |
013.txt |
AC |
143 ms |
15360 KB |
014.txt |
AC |
144 ms |
15360 KB |
015.txt |
AC |
146 ms |
15360 KB |
016.txt |
AC |
143 ms |
15360 KB |
017.txt |
AC |
144 ms |
15360 KB |
018.txt |
AC |
144 ms |
15360 KB |
019.txt |
AC |
144 ms |
15360 KB |
020.txt |
AC |
144 ms |
15360 KB |
021.txt |
AC |
12 ms |
6528 KB |
022.txt |
AC |
127 ms |
13312 KB |
023.txt |
AC |
57 ms |
10880 KB |
024.txt |
AC |
23 ms |
8576 KB |
025.txt |
AC |
77 ms |
11008 KB |
026.txt |
AC |
15 ms |
6528 KB |
027.txt |
AC |
102 ms |
13184 KB |
028.txt |
AC |
50 ms |
10752 KB |
029.txt |
AC |
49 ms |
10752 KB |
030.txt |
AC |
50 ms |
10752 KB |
031.txt |
AC |
103 ms |
13056 KB |
032.txt |
AC |
64 ms |
10880 KB |
033.txt |
AC |
64 ms |
12928 KB |
034.txt |
AC |
111 ms |
13184 KB |
035.txt |
AC |
20 ms |
8576 KB |
036.txt |
AC |
125 ms |
15232 KB |
037.txt |
AC |
96 ms |
13056 KB |
038.txt |
AC |
25 ms |
8576 KB |
039.txt |
AC |
72 ms |
12928 KB |
040.txt |
AC |
65 ms |
12928 KB |
041.txt |
AC |
125 ms |
15232 KB |
042.txt |
AC |
79 ms |
15360 KB |
043.txt |
AC |
78 ms |
15360 KB |
044.txt |
AC |
160 ms |
15360 KB |
045.txt |
AC |
2 ms |
4352 KB |
046.txt |
AC |
21 ms |
9216 KB |
047.txt |
AC |
151 ms |
15360 KB |
048.txt |
AC |
20 ms |
9216 KB |
049.txt |
AC |
23 ms |
9216 KB |
050.txt |
AC |
32 ms |
9216 KB |
051.txt |
AC |
51 ms |
9216 KB |
052.txt |
AC |
76 ms |
9216 KB |
053.txt |
AC |
109 ms |
11264 KB |
054.txt |
AC |
144 ms |
13312 KB |
055.txt |
AC |
17 ms |
9216 KB |
056.txt |
AC |
21 ms |
9216 KB |
057.txt |
AC |
30 ms |
9216 KB |
058.txt |
AC |
45 ms |
9216 KB |
059.txt |
AC |
69 ms |
9216 KB |
060.txt |
AC |
99 ms |
11264 KB |
061.txt |
AC |
134 ms |
13312 KB |
062.txt |
AC |
75 ms |
13312 KB |
063.txt |
AC |
70 ms |
13312 KB |
example0.txt |
AC |
3 ms |
6400 KB |
example1.txt |
AC |
3 ms |
6400 KB |