Submission #1000640

#TimeUsernameProblemLanguageResultExecution timeMemory
1000640vjudge1Safety (NOI18_safety)C++17
100 / 100
116 ms23324 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 3e5 + 30, MOD = 1e9 + 7; #define int ll int n,h; ll a[N]; multiset<ll> l,r; ll addl = 0,addr = 0; void test(){ cin >> n >> h; for(int i = 1;i <= n;i++){ cin >> a[i]; } l.insert(a[1]); r.insert(a[1]); ll H = 0; for(int i = 2;i <= n;i++){ addl -= h; addr += h; ll L = (*l.rbegin()) + addl,R = (*r.begin()) + addr; if(a[i] >= L && a[i] <= R){ l.insert(a[i] - addl); r.insert(a[i] - addr); }else if(a[i] >R){ H += (a[i] - R); r.erase(r.find(R - addr)); l.insert(R - addl); r.insert(a[i] - addr);r.insert(a[i] - addr); }else{ H += (L - a[i]); l.erase(l.find(L - addl)); r.insert(L - addr); l.insert(a[i] - addl); l.insert(a[i] - addl); } // cout << H << '\n'; // cout << "-"; // for(int j:l){ // cout << j+addl<< ' '; // } // cout << '\n'; // cout << "+"; // for(int j:r){ // cout << j+addr << ' '; // } // cout << '\n'; // cout << "___________________________________\n"; } assert(*r.begin()+addr >= 0); cout << H << '\n'; } signed main() { ios_base::sync_with_stdio(false);cin.tie(0); int t = 1; // cin >> t; while(t--){ test(); } }
#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...