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
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
AC × 2
AC × 22
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