Submission #492251

#TimeUsernameProblemLanguageResultExecution timeMemory
492251cuiaoxiangSafety (NOI18_safety)C++17
100 / 100
68 ms6316 KiB
#define LOCAL #define _USE_MATH_DEFINES #include <array> #include <cassert> #include <cstdio> #include <cstring> #include <iostream> #include <iomanip> #include <string> #include <sstream> #include <vector> #include <queue> #include <stack> #include <list> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <algorithm> #include <complex> #include <cmath> #include <numeric> #include <bitset> #include <functional> #include <random> #include <ctime> using namespace std; template <typename A, typename B> ostream& operator <<(ostream& out, const pair<A, B>& a) { out << "(" << a.first << "," << a.second << ")"; return out; } template <typename T, size_t N> ostream& operator <<(ostream& out, const array<T, N>& a) { out << "["; bool first = true; for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]"; return out; } template <typename T> ostream& operator <<(ostream& out, const vector<T>& a) { out << "["; bool first = true; for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]"; return out; } template <typename T, class Cmp> ostream& operator <<(ostream& out, const set<T, Cmp>& a) { out << "{"; bool first = true; for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}"; return out; } template <typename U, typename T, class Cmp> ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) { out << "{"; bool first = true; for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}"; return out; } #ifdef LOCAL #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__) #else #define trace(...) 42 #endif template <typename Arg1> void __f(const char* name, Arg1&& arg1){ cerr << name << ": " << arg1 << endl; } template <typename Arg1, typename... Args> void __f(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << ": " << arg1 << " |"; __f(comma + 1, args...); } template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); } template <class T, class... D> auto vect(const T& v, int n, D... m) { return vector<decltype(vect(v, m...))>(n, vect(v, m...)); } typedef long long int64; typedef pair<int, int> ii; #define SZ(x) (int)((x).size()) template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2; const int MOD = 1e9 + 7; mt19937 mrand(random_device{}()); int rnd(int x) { return mrand() % x; } struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); }; } fast_ios_; template <typename T> struct slope_trick { T min_f; priority_queue<T, vector<T>, less<>> L; priority_queue<T, vector<T>, greater<>> R; T add_l, add_r; void pushR(const T& x) { R.push(x - add_r); } T topR() const { if (R.empty()) return inf<T>; return R.top() + add_r; } T popR() { T ret = topR(); if (!R.empty()) R.pop(); return ret; } void pushL(const T& x) { L.push(x - add_l); } T topL() const { if (L.empty()) return -inf<T>; return L.top() + add_l; } T popL() { T ret = topL(); if (!L.empty()) L.pop(); return ret; } size_t size() { return L.size() + R.size(); } slope_trick() : min_f(0), add_l(0), add_r(0) {} // f(x) += a void add_all(const T& a) { min_f += a; } // add \_ // f(x) += max(a - x, 0) void add_a_minus_x(const T& a) { min_f += max(T(0), a - topR()); pushR(a); pushL(popR()); } // add _/ // f(x) += max(x - a, 0) void add_x_minus_a(const T& a) { min_f += max(T(0), topL() - a); pushL(a); pushR(popL()); } // add \/ // f(x) += abs(x - a) void add_abs(const T& a) { add_a_minus_x(a); add_x_minus_a(a); } // \/ -> \_ // f_new(x) = min f(y) (y <= x) void clear_right() { while (!R.empty()) R.pop(); } // \/ -> _/ // f_new(x) = min f(y) (y >= x) void clear_left() { while (!L.empty()) L.pop(); } // \/ -> \_/ // f_new(x) = min f(y) (x-b <= y <= x-a) void expand(const T& a, const T& b) { assert(a <= b); add_l += a; add_r += b; } // \/. -> .\/ // f_new(x) = f(x - a) void shift(const T& a) { expand(a, a); } // L, R will be emptied. T get(const T& x) { T ret = min_f; while (!L.empty()) ret += max(T(0), popL() - x); while (!R.empty()) ret += max(T(0), x - popR()); return ret; } void merge(slope_trick& other) { if (other.size() > size()) { swap(other.L, L); swap(other.R, R); swap(other.add_l, add_l); swap(other.add_r, add_r); swap(other.min_f, min_f); } while (!other.R.empty()) add_x_minus_a(other.popR()); while (!other.L.empty()) add_a_minus_x(other.popL()); min_f += other.min_f; } }; int main() { int n, m; cin >> n >> m; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; slope_trick<int64> st; st.add_abs(a[0]); for (int i = 1; i < n; ++i) { st.expand(-m, m); st.add_abs(a[i]); } cout << st.min_f << '\n'; return 0; }
#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...