Submission #1113787

#TimeUsernameProblemLanguageResultExecution timeMemory
1113787Zero_OPBuilding Bridges (CEOI17_building)C++14
0 / 100
167 ms89520 KiB
//Just some random thing in my mind #include <bits/stdc++.h> using namespace std; const long long inf = 4e18; struct line{ long long a, b, p; line(long long a = 0, long long b = 0, long long p = 0) : a(a), b(b), p(p) {} long long eval(long long x){ return a * x + b; } bool operator < (const long long& o) const { return p < o; } friend bool operator < (const line& d1, const line& d2){ return make_pair(d1.a, d1.b) > make_pair(d2.a, d2.b); } }; long long divi(long long a, long long b){ return a / b - ((a % b) != 0 && (a ^ b) < 0); } void isect(line& d1, const line& d2){ if(d1.a == d2.a) d1.p = (d1.b < d2.b ? inf : -inf); else d1.p = divi(d2.b - d1.b, d1.a - d2.a); } struct convex_hull_trick{ deque<line> v; convex_hull_trick() : v() {} void add(long long a, long long b){ line d(a, b, inf); if(!v.empty()) isect(v.back(), d); while((int)v.size() > 1 && v[(int)v.size() - 2].p >= v.back().p){ v.pop_back(); isect(v.back(), d); } v.push_back(d); } // long long query(long long x){ // int id = lower_bound(v.begin(), v.end(), x) - v.begin(); // return v[id].eval(x); // } long long query(long long x){ while((int)v.size() > 1 && v[0].eval(x) >= v[1].eval(x)) v.pop_front(); return v[0].eval(x); } }; template<typename T> void merge_sort(vector<T>& a, const vector<T>& b){ vector<T> c; int i = 0, j = 0; while(i < (int)a.size() || j < (int)b.size()){ if(i == (int)a.size()) c.emplace_back(b[j++]); else if(j == (int)b.size()) c.emplace_back(a[i++]); else if(a[i] < b[j]) c.emplace_back(a[i++]); else c.emplace_back(b[j++]); } swap(a, c); } const int MAX = 1e5 + 5; int N, timerNodes, ln[MAX * 2], rn[MAX * 2]; long long dp[MAX], h[MAX], w[MAX]; vector<line> lines[MAX * 2]; vector<pair<int, int>> queries[MAX * 2]; int build(int l, int r){ if(l == r) { ++timerNodes; queries[timerNodes].emplace_back(-2 * h[l], l); return timerNodes; } int mid = l + r >> 1, cur = ++timerNodes; ln[cur]= build(l, mid); rn[cur] = build(mid + 1, r); queries[cur]= queries[ln[cur]]; merge_sort(queries[cur], queries[rn[cur]]); return cur; } void solve(int l, int r, int cur){ if(l == r) { lines[cur].emplace_back(h[l], h[l] * h[l] + dp[l] - w[l]); return; } int mid = l + r >> 1; solve(l, mid, ln[cur]); convex_hull_trick cht; for(auto d : lines[ln[cur]]) cht.add(d.a, d.b); for(auto [slope, i] : queries[rn[cur]]){ dp[i] = min(dp[i], cht.query(slope) + w[i - 1] + h[i] * h[i]); } solve(mid + 1, r, rn[cur]); lines[cur] = lines[ln[cur]]; merge_sort(lines[cur], lines[rn[cur]]); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef LOCAL freopen("task.inp", "r", stdin); freopen("task.out", "w", stdout); #endif // LOCAL cin >> N; for(int i = 1; i <= N; ++i) cin >> h[i]; for(int i = 1; i <= N; ++i) cin >> w[i], w[i] += w[i - 1]; for(int i = 2; i <= N; ++i) dp[i] = inf; int root = build(1, N); solve(1, N, root); for(int i = 1; i <= N; ++i){ cout << dp[i] << ' '; } cout << '\n'; cout << dp[N] << '\n'; return 0; }

Compilation message (stderr)

building.cpp: In function 'int build(int, int)':
building.cpp:80:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |     int mid = l + r >> 1, cur = ++timerNodes;
      |               ~~^~~
building.cpp: In function 'void solve(int, int, int)':
building.cpp:94:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |     int mid = l + r >> 1;
      |               ~~^~~
building.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |     for(auto [slope, i] : queries[rn[cur]]){
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...