Submission #8908647
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])); // cout<<"Push "<<A[i]<<' '<<A[i+1]<<'\n'; } 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){ // cout<<pq.top().f<<'\n'; while(SZ(pq) && pq.top().f == i-1){ pi p = pq.top();pq.pop(); // cout<<"Remove "<<p.s<<' '<<p.f<<'\n'; save -= (p.f+M-p.s)%M; ++save; } save += SZ(pq); for (auto x:V[i-1]){ if(i-1>x)pq.push(mp(x+M,i-1)); else pq.push(mp(x,i-1)); // cout<<i-1<<' '<<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 | 700 |
Code Size | 1290 Byte |
Status | AC |
Exec Time | 50 ms |
Memory | 7284 KB |
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 | 13 ms | 3328 KB |
half1.txt | AC | 6 ms | 2816 KB |
half2.txt | AC | 23 ms | 3964 KB |
half3.txt | AC | 35 ms | 4600 KB |
half4.txt | AC | 38 ms | 5240 KB |
min_m.txt | AC | 2 ms | 2560 KB |
min_n.txt | AC | 3 ms | 2560 KB |
mx0.txt | AC | 49 ms | 7284 KB |
mx1.txt | AC | 49 ms | 7284 KB |
mx2.txt | AC | 50 ms | 7284 KB |
rnd0.txt | AC | 2 ms | 2560 KB |
rnd1.txt | AC | 2 ms | 2560 KB |
rnd2.txt | AC | 4 ms | 2816 KB |
rnd3.txt | AC | 10 ms | 3328 KB |
rnd4.txt | AC | 35 ms | 4984 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 | 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 |