Submission #1816743
Source Code Expand
#include<bits/stdc++.h>
#define maxn 200100
#define inf 1010000007
using namespace std;
typedef pair<int,int> par;
struct data{
int lc,rc,atg;
par p;
}s[maxn*60];
int n,a[maxn],ptr,rt;
par qry(int& o,int l,int r,int ql,int qr){
if(!o)s[o=++ptr].p=par(l,l);
if(ql<=l&&r<=qr)
return s[o].p;
int mid=l+r>>1;
par ans(inf,inf);
if(ql<=mid)ans=min(ans,qry(s[o].lc,l,mid,ql,qr));
if(qr>mid)ans=min(ans,qry(s[o].rc,mid+1,r,ql,qr));
return par(ans.first+s[o].atg,ans.second);
}
void mdy(int &o,int l,int r,int ql,int qr){
if(ql>qr)return ;
if(!o)s[o=++ptr].p=par(l,l);
if(ql<=l&&r<=qr){
s[o].atg++;
s[o].p.first++;
return ;
}
int mid=l+r>>1;
if(ql<=mid)mdy(s[o].lc,l,mid,ql,qr);
if(qr>mid)mdy(s[o].rc,mid+1,r,ql,qr);
s[o].p=min(s[o].lc?s[s[o].lc].p:par(inf,inf),s[o].rc?s[s[o].rc].p:par(inf,inf));
s[o].p=par(s[o].p.first+s[o].atg,s[o].p.second);
}
int main(){
scanf("%d",&n);
long long ans=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
int x=qry(rt,1,inf,a[i],inf).first;
ans+=x-a[i],mdy(rt,1,inf,1,x-1);
}
printf("%lld",ans);
}
Submission Info
Submission Time
2017-11-29 22:14:22+0900
Task
B - Increment and Swap
User
yfzcsc
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1099 Byte
Status
WA
Exec Time
368 ms
Memory
235648 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:36:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:39:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 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
WA
267 ms
235520 KB
001.txt
WA
267 ms
235520 KB
002.txt
WA
272 ms
235520 KB
003.txt
WA
268 ms
235520 KB
004.txt
WA
281 ms
235520 KB
005.txt
WA
276 ms
235520 KB
006.txt
WA
278 ms
235648 KB
007.txt
WA
288 ms
235520 KB
008.txt
WA
283 ms
235520 KB
009.txt
WA
284 ms
235520 KB
010.txt
WA
286 ms
235520 KB
011.txt
WA
292 ms
235520 KB
012.txt
WA
290 ms
235520 KB
013.txt
WA
291 ms
235520 KB
014.txt
WA
295 ms
235520 KB
015.txt
WA
300 ms
235520 KB
016.txt
WA
307 ms
235520 KB
017.txt
WA
312 ms
235520 KB
018.txt
WA
305 ms
235520 KB
019.txt
WA
310 ms
235520 KB
020.txt
WA
314 ms
235520 KB
021.txt
WA
89 ms
234880 KB
022.txt
WA
261 ms
235520 KB
023.txt
WA
161 ms
235136 KB
024.txt
WA
106 ms
234880 KB
025.txt
WA
192 ms
235264 KB
026.txt
WA
93 ms
234880 KB
027.txt
WA
224 ms
235264 KB
028.txt
WA
150 ms
235008 KB
029.txt
WA
145 ms
235008 KB
030.txt
WA
147 ms
235008 KB
031.txt
WA
230 ms
235264 KB
032.txt
WA
173 ms
235136 KB
033.txt
WA
173 ms
235136 KB
034.txt
WA
244 ms
235392 KB
035.txt
WA
101 ms
234880 KB
036.txt
WA
265 ms
235392 KB
037.txt
WA
222 ms
235264 KB
038.txt
WA
115 ms
234880 KB
039.txt
WA
186 ms
235136 KB
040.txt
WA
175 ms
235136 KB
041.txt
WA
267 ms
235392 KB
042.txt
AC
253 ms
235520 KB
043.txt
AC
257 ms
235520 KB
044.txt
WA
289 ms
235520 KB
045.txt
AC
67 ms
234752 KB
046.txt
WA
240 ms
235520 KB
047.txt
WA
368 ms
235520 KB
048.txt
WA
201 ms
235520 KB
049.txt
WA
224 ms
235520 KB
050.txt
WA
244 ms
235520 KB
051.txt
WA
249 ms
235520 KB
052.txt
WA
254 ms
235520 KB
053.txt
WA
261 ms
235520 KB
054.txt
WA
279 ms
235520 KB
055.txt
WA
200 ms
235520 KB
056.txt
WA
224 ms
235520 KB
057.txt
WA
245 ms
235520 KB
058.txt
WA
250 ms
235520 KB
059.txt
WA
252 ms
235520 KB
060.txt
WA
258 ms
235520 KB
061.txt
WA
275 ms
235520 KB
062.txt
AC
255 ms
235520 KB
063.txt
WA
255 ms
235520 KB
example0.txt
AC
67 ms
234752 KB
example1.txt
AC
67 ms
234752 KB