Submission #1254864

#TimeUsernameProblemLanguageResultExecution timeMemory
1254864magic_tripSafety (NOI18_safety)C++20
100 / 100
35 ms5204 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma optimize("unroll-loops") #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define all(x) x.begin(), x.end() #define rll(x) x.rbegin(), x.rend() #define COMP(x) x.erase(unique(all(x)), x.end()) #define MOD 1000000007 #define MOD2 998244353 #define sz(x) (ll)x.size() typedef __int128_t lll; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll,ll> pll; typedef pair<ll, pll> PP; const ll Lnf = 2e18; ll n, h; ll dx_L, dx_R; ll A[202020]; priority_queue<ll> pq_L; //이 값에다가 +dx_L을 해야 원래 값이 나옴. priority_queue<ll,vector<ll>,greater<ll>> pq_R; //마찬가지 int main(){ fast; cin>>n>>h; ll ans = 0; for(int i = 1 ; i <= n ; i++){ cin>>A[i]; if(!sz(pq_L) and !sz(pq_R)){ pq_L.push(A[i]); pq_R.push(A[i]); continue; } dx_L -= h; dx_R += h; if(A[i] < pq_L.top() + dx_L){ ans += abs(pq_L.top() + dx_L - A[i]); pq_R.push(pq_L.top() + dx_L - dx_R); pq_L.pop(); pq_L.push(A[i] - dx_L); pq_L.push(A[i] - dx_L); } else if(A[i] > pq_R.top() + dx_R){ ans += abs(pq_R.top() + dx_R - A[i]); pq_L.push(pq_R.top() + dx_R - dx_L); pq_R.pop(); pq_R.push(A[i] - dx_R); pq_R.push(A[i] - dx_R); } else{ pq_L.push(A[i] - dx_L); pq_R.push(A[i] - dx_R); } // cout<<pq_L.top()+dx_L<<" "<<pq_R.top()+dx_R<<" "<<ans<<endl; } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...