Submission #8940223
Source Code Expand
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <assert.h>
#include <memory.h>
#include <queue>
#include <string.h>
using namespace std;
#define N 100002
int a[N],val[N];
long long ret[N];
int f(int x,int y,int m) {
if(x<y) {
return y-x;
}
return m + y-x;
}
vector<pair<int,int> > st[N];
void solve() {
int n,m;scanf("%d %d ", &n,&m);
for(int i=0;i<n;++i) {
scanf("%d ", &a[i]);
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
long long curValue = 0;
for(int i=0;i<n-1;++i) {
int val = f(a[i],a[i+1],m);
if(a[i]<a[i+1]) {
curValue += val;
st[a[i]].push_back(make_pair(a[i+1],val));
} else {
curValue += a[i+1];
pq.push(make_pair(a[i+1],val));
st[a[i]].push_back(make_pair(m+2,val));
}
}
long long R = 1e18;
for(int i=1;i<=m;++i) {
while(!pq.empty()) {
int lim = pq.top().first, val = pq.top().second;
if(lim<i) {
curValue += val;
pq.pop();
} else {
break;
}
}
R = min(R, curValue);
while(!st[i].empty()) {
pq.push(st[i].back());
++curValue;
st[i].pop_back();
}
curValue -= pq.size();
}
printf("%lld\n", R);
}
int main() {
//freopen("input.txt","r",stdin);
solve();
return 0;
}
Submission Info
Submission Time
2019-12-14 02:08:53+0900
Task
E - guruguru
User
ffresh
Language
C++14 (GCC 5.4.1)
Score
700
Code Size
1396 Byte
Status
AC
Exec Time
30 ms
Memory
6132 KB
Compile Error
./Main.cpp: In function ‘void solve()’:
./Main.cpp:22:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int n,m;scanf("%d %d ", &n,&m);
^
./Main.cpp:24:24: 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
700 / 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
9 ms
3328 KB
half1.txt
AC
5 ms
2816 KB
half2.txt
AC
14 ms
3964 KB
half3.txt
AC
22 ms
4212 KB
half4.txt
AC
23 ms
4476 KB
min_m.txt
AC
2 ms
2560 KB
min_n.txt
AC
2 ms
2560 KB
mx0.txt
AC
30 ms
6132 KB
mx1.txt
AC
30 ms
6132 KB
mx2.txt
AC
30 ms
6132 KB
rnd0.txt
AC
2 ms
2560 KB
rnd1.txt
AC
2 ms
2560 KB
rnd2.txt
AC
4 ms
2688 KB
rnd3.txt
AC
7 ms
3072 KB
rnd4.txt
AC
24 ms
4220 KB
rnd5.txt
AC
3 ms
2688 KB
rnd6.txt
AC
2 ms
2560 KB
rnd7.txt
AC
3 ms
2688 KB
rnd8.txt
AC
5 ms
2816 KB
rnd9.txt
AC
2 ms
2560 KB
sample1.txt
AC
2 ms
2560 KB
sample2.txt
AC
2 ms
2560 KB