제출 #739518

#제출 시각아이디문제언어결과실행 시간메모리
739518boris_mihovAliens (IOI16_aliens)C++17
100 / 100
135 ms6832 KiB
#include "aliens.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> #include <queue> typedef long long llong; const int MAXN = 100000 + 10; const int INF = 1e9; int n, m, k; struct Interval { int l, r; inline friend bool operator < (const Interval &a, const Interval &b) { return a.l < b.l || (a.l == b.l && a.r < b.r); } }; struct CHT { struct Line { llong x, y; int cntPenalties; int to; std::pair <llong,int> getValue(int at) { return {x * at + y, cntPenalties}; } }; llong intersect(Line a, Line b) { if (a.y >= b.y) { return INF; } return (b.y - a.y) / (a.x - b.x) - ((b.y - a.y) % (a.x - b.x) == 0 && b.cntPenalties < a.cntPenalties); } std::deque <Line> dq; void reset() { dq.clear(); } void push(Line toPush) { while (dq.size() && dq.front().getValue(dq.front().to) > toPush.getValue(dq.front().to)) { dq.pop_front(); } if (dq.empty()) { dq.push_front(toPush); } else { llong where = intersect(toPush, dq.front()); if (where <= m) dq.push_front({toPush.x, toPush.y, toPush.cntPenalties, where}); } } std::pair <llong,int> find(int at) { while (dq.size() >= 2 && dq[dq.size() - 2].to >= at) { dq.pop_back(); } assert(dq.size()); return dq.back().getValue(at); } }; CHT cht; std::vector <Interval> v; std::pair <llong,int> dp[MAXN]; std::pair <llong,int> check(llong penalty) { cht.reset(); cht.push({-2 * v.back().r, 1LL * v.back().r * v.back().r + penalty, 1, m}); for (int idx = v.size() - 1 ; idx >= 0 ; --idx) { dp[idx] = cht.find(v[idx].l); dp[idx].first += 1LL * v[idx].l * v[idx].l; if (idx != 0) { llong toRemove = std::max(0, v[idx - 1].r - v[idx].l); toRemove *= toRemove; cht.push({-2 * v[idx - 1].r, 1LL * v[idx - 1].r * v[idx - 1].r + dp[idx].first - toRemove + penalty, dp[idx].second + 1, m}); } } return dp[0]; } llong take_photos(int N, int M, int K, std::vector <int> x, std::vector <int> y) { n = N; m = M; k = K; std::vector <Interval> sorted; for (int i = 0 ; i < n ; ++i) { sorted.push_back({std::min(x[i], y[i]), std::max(x[i], y[i]) + 1}); } std::sort(sorted.begin(), sorted.end()); for (const Interval &curr : sorted) { while (v.size() && v.back().l == curr.l && curr.r >= v.back().r) { v.pop_back(); } if (v.empty() || v.back().r < curr.r) { v.push_back(curr); } } k = std::min(k, (int)v.size()); llong l = -1, r = 1LL * m * m, mid; while (l < r - 1) { mid = (l + r) / 2; auto res = check(mid); if (res.second == k) { return res.first - k * mid; } if (res.second > k) l = mid; else r = mid; } auto resL = check(l); auto resR = check(r); llong fL = resL.first - resL.second * l; llong fR = resR.first - resR.second * r; return fL + (fR - fL) * (resL.second - k) / (resL.second - resR.second); }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In member function 'void CHT::push(CHT::Line)':
aliens.cpp:66:85: warning: narrowing conversion of 'where' from 'llong' {aka 'long long int'} to 'int' [-Wnarrowing]
   66 |             if (where <= m) dq.push_front({toPush.x, toPush.y, toPush.cntPenalties, where});
      |                                                                                     ^~~~~
#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...