Submission #8941893
Source Code Expand
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int n, m;
const int maxn = 4e5 + 5;
int a[maxn];
typedef long long LL;
LL c[2][maxn];
void add(int id, int x, int d){
for(int i = x;i < maxn;i += i & -i){
c[id][i] += d;
}
}
LL sum(int id, int x){
LL res = 0;
for(int i = x;i > 0;i -= i & -i){
res += c[id][i];
}
return res;
}
void add1(int id, int l, int r, int v){
add(id, l, v);
add(id, r + 1, -v);
}
LL query(int x){
return sum(0, x) * x + sum(1, x);
}
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
scanf("%d", &a[i]);
}
for(int i = 1;i < n;i++){
if(a[i + 1] > a[i]){
add1(1, 1, 2 * m, a[i + 1] - a[i]);
add1(1, a[i] + 1, a[i + 1], a[i] + 1);
add1(1, a[i] + 1 + m, a[i + 1] + m, a[i] + 1 + m);
add1(0, a[i] + 1, a[i + 1], -1);
add1(0, a[i] + 1 + m, a[i + 1] + m, -1);
}else{
add1(1, 1, 2 * m, a[i + 1] + m - a[i]);
add1(1, a[i] + 1, a[i + 1] + m, a[i] + 1);
add1(0, a[i] + 1, a[i + 1] + m, -1);
}
}
for(int i = 1;i <= 2 * m;i++){
//cout << i << " " << sum(0, i) << " " << sum(1, i) << endl;
}
LL ans = query(1);
for(int i = 2;i <= 2 * m;i++){
//cout << ans << endl;
ans = min(ans, query(i));
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time
2019-12-14 10:44:10+0900
Task
E - guruguru
User
Yufan_Huang
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1513 Byte
Status
WA
Exec Time
35 ms
Memory
6272 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:41:27: 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 / 700
Status
Set Name
Test Cases
Sample
sample1.txt, sample2.txt
All
half0.txt, half1.txt, half2.txt, half3.txt, half4.txt, min_m.txt, min_n.txt, mx0.txt, mx1.txt, mx2.txt, rnd0.txt, rnd1.txt, rnd2.txt, rnd3.txt, rnd4.txt, rnd5.txt, rnd6.txt, rnd7.txt, rnd8.txt, rnd9.txt, sample1.txt, sample2.txt
Case Name
Status
Exec Time
Memory
half0.txt
AC
12 ms
4864 KB
half1.txt
AC
8 ms
4992 KB
half2.txt
AC
19 ms
5120 KB
half3.txt
AC
28 ms
4992 KB
half4.txt
AC
30 ms
5376 KB
min_m.txt
AC
2 ms
4352 KB
min_n.txt
AC
5 ms
4352 KB
mx0.txt
WA
35 ms
6272 KB
mx1.txt
WA
34 ms
6272 KB
mx2.txt
WA
35 ms
6272 KB
rnd0.txt
AC
3 ms
4480 KB
rnd1.txt
AC
2 ms
4480 KB
rnd2.txt
WA
4 ms
4608 KB
rnd3.txt
WA
8 ms
4608 KB
rnd4.txt
WA
29 ms
4736 KB
rnd5.txt
AC
3 ms
4352 KB
rnd6.txt
AC
2 ms
4352 KB
rnd7.txt
WA
3 ms
4736 KB
rnd8.txt
WA
5 ms
4480 KB
rnd9.txt
AC
2 ms
4480 KB
sample1.txt
AC
2 ms
4352 KB
sample2.txt
AC
2 ms
4352 KB