Submission #8907926
Source Code Expand
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vi; typedef pair<ll,ll> pi; typedef vector<pi> vpi; typedef long double ld; #define pb emplace_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define ALL(x) x.begin(), x.end() #define SZ(x) (int)x.size() #define f first #define s second #define MAXN 100010 priority_queue<pi,vpi,greater<pi>> pq; vi V[MAXN]; ll N,M; ll W,ans; ll A[MAXN]; ll save; int main(){ cin>>N>>M; for (ll i=1;i<=N;++i){ cin>>A[i]; } for (ll i=1;i<N;++i){ ll w = (A[i+1]+M-A[i])%M; W += w; if (A[i+1] < A[i]){ save += (M-A[i]); pq.push(mp(A[i+1], A[i])); }else{ V[A[i]].pb(A[i+1]); } } ll sv = 0; // cout<<"Save 1 "<<W-save<<'\n'; sv = max(sv,save); for (ll i=2;i<=M;++i){ while(SZ(pq) && pq.top().f < i){ pi p = pq.top();pq.pop(); // cout<<"Remove "<<p.f<<' '<<p.s<<'\n'; save -= (p.f+M-p.s)%M; ++save; } save += SZ(pq); for (auto x:V[i-1]){ pq.push(mp(x,i-1)); // cout<<"Push "<<i<<' '<<x<<'\n'; } // cout<<"Save "<<i<<' '<<W-save<<'\n'; sv = max(sv,save); } cout<<W-sv<<'\n'; }
Submission Info
Submission Time | |
---|---|
Task | E - guruguru |
User | dvdg6566 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1188 Byte |
Status | WA |
Exec Time | 45 ms |
Memory | 5492 KB |
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 | 3328 KB |
half1.txt | AC | 6 ms | 2816 KB |
half2.txt | AC | 21 ms | 3836 KB |
half3.txt | AC | 33 ms | 4344 KB |
half4.txt | AC | 35 ms | 4856 KB |
min_m.txt | AC | 2 ms | 2560 KB |
min_n.txt | AC | 3 ms | 2560 KB |
mx0.txt | WA | 44 ms | 5492 KB |
mx1.txt | WA | 44 ms | 5492 KB |
mx2.txt | WA | 45 ms | 5492 KB |
rnd0.txt | AC | 2 ms | 2560 KB |
rnd1.txt | AC | 2 ms | 2560 KB |
rnd2.txt | WA | 4 ms | 2688 KB |
rnd3.txt | WA | 10 ms | 3200 KB |
rnd4.txt | WA | 33 ms | 4712 KB |
rnd5.txt | WA | 3 ms | 2688 KB |
rnd6.txt | WA | 2 ms | 2560 KB |
rnd7.txt | WA | 3 ms | 2688 KB |
rnd8.txt | WA | 6 ms | 2816 KB |
rnd9.txt | AC | 2 ms | 2560 KB |
sample1.txt | AC | 2 ms | 2560 KB |
sample2.txt | AC | 2 ms | 2560 KB |