Submission #1242052

#TimeUsernameProblemLanguageResultExecution timeMemory
1242052Zero_OPSafety (NOI18_safety)C++17
100 / 100
50 ms3752 KiB
//CAUTION : this template is only suitable with C++17 (above) and home training, do not abuse when practicing offline #include <bits/stdc++.h> using namespace std; //Benq inspires me lol #define tcT template<class T #define tcTU tcT, class U //pairs #define mp make_pair #define mt make_tuple #define ff first #define ss second //vectors #define sz(v) (int)v.size() #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) #define pb push_back #define eb emplace_back #define compact(v) v.erase(unique(all(v)), end(v)) tcT> int lwb(const vector<T>& a, const T& b){ return int(lower_bound(all(a), b) - begin(a)); } tcT> int upb(const vector<T>& a, const T& b){ return int(upper_bound(all(a), b) - begin(a)); } //loops (warning : ONLY for int) #define rep(i, l, r) for(int i = (l); i < (r); ++i) #define FOR(i, l, r) for(int i = (l); i <= (r); ++i) #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif //LOCAL //data types using ll = long long; using db = double; using ld = long double; using pi = pair<int, int>; using pl = pair<ll, ll>; using vi = vector<int>; using vl = vector<ll>; using vb = vector<bool>; using vd = vector<db>; using vc = vector<char>; using vstr = vector<string>; using vpi = vector<pi>; using vpl = vector<pl>; tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>; tcT> using max_heap = priority_queue<T>; //bitwise operations #define popcount(x) __builtin_popcountll(x) //count bits #define BIT(k) (1LL << k) //bit k-th //functions tcT> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; } tcT> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; } tcT> T ceil_div(T a, T b){ return (a / b) + ((a ^ b) > 0 && a % b); } tcT> T floor_div(T a, T b){ return (a / b) - ((a ^ b) < 0 && a % b); } tcT> void safe_erase(vector<T>& a, T x){ auto it = find(all(a), x); if(it != a.end()) a.erase(it); } #ifdef LOCAL //for checking time elapsed const auto start_time = std::chrono::high_resolution_clock::now(); db time_elapsed(){ return chrono::duration<db>(std::chrono::high_resolution_clock::now() - start_time).count(); } #endif //LOCAL void setIO(){ ios_base::sync_with_stdio(0); cin.tie(0); #define task "task" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); // freopen(task".out", "w", stdout); } } tcT> struct SlopeTrick{ max_heap<T> L; min_heap<T> R; T min_f, shifted_L, shifted_R; SlopeTrick() : min_f(0), shifted_L(0), shifted_R(0), L(), R() {} //make sure l0 <= r0 void self_balance(){ while(!L.empty() && !R.empty()){ T l0 = L.top() + shifted_L; T r0 = R.top() + shifted_R; if(l0 <= r0) break; min_f += l0 - r0; L.pop(); R.pop(); L.push(r0 - shifted_L); R.push(l0 - shifted_R); } } //add a function max(0, l - x) void add_linear_l(T l){ L.push(l - shifted_L); self_balance(); } //add a function max(0, x - r) void add_linear_r(T r){ R.push(r - shifted_R); self_balance(); } //add a function |x - a| void add_abs(T a){ add_linear_l(a); add_linear_r(a); } void shift(T a){ shifted_L += a; shifted_R += a; } T query(){ return min_f; } void make_sliding_window(T a, T b){ shifted_L += a; shifted_R += b; } void make_prefix_minimum(){ min_heap<T>().swap(R); } void make_suffix_minimum(){ max_heap<T>().swap(L); } }; void testcase(int n_case){ int N, H; cin >> N >> H; SlopeTrick<ll> st; rep(i, 0, N){ int x; cin >> x; st.add_abs(x); st.make_sliding_window(-H, +H); } cout << st.min_f << '\n'; } int main(){ setIO(); int T = 1; // cin >> T; rep(i, 0, T) testcase(i); #ifdef LOCAL cerr << '\n' << "Execution time : " << (time_elapsed() * 1000.0) << " ms"; #endif //LOCAL return 0; }

Compilation message (stderr)

safety.cpp: In function 'void setIO()':
safety.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...