이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " " << x << endl
#define _ << " " <<
using llint = long long;
const int MAXN = 5e4 + 5;
const llint INF = 1e17;
int n, m, k;
vector<pair<int, int>> I, P;
vector<llint> A, B;
vector<int> hull;
struct Event {
int x, type, id;
Event() {}
Event(int x, int type, int id) : x(x), type(type), id(id) {}
friend bool operator<(const Event &A, const Event &B) {
if (A.x == B.x) return A.type < B.type;
return A.x < B.x;
}
};
vector<pair<int, int>> get_intervals(int n, const vector<int> &r,
const vector<int> &c) {
vector<Event> e;
for (int i = 0; i < n; ++i) {
int lo = min(r[i], c[i]);
int hi = max(r[i], c[i]);
e.emplace_back(lo, 0, i);
e.emplace_back(hi, 1, i);
}
sort(e.begin(), e.end());
multiset<int> ms;
vector<pair<int, int>> ret;
for (const auto &p : e) {
if (p.type == 0) {
ms.insert(p.x);
continue;
}
int lo = min(r[p.id], c[p.id]);
ms.erase(ms.find(lo));
if (ms.empty() || *ms.begin() > lo) ret.emplace_back(lo, p.x);
}
return ret;
}
// y = ax + b = cx + d
// x(a - c) == d - b
double intersect(pair<llint, llint> &A, pair<llint, llint> &B) {
return (double) (B.second - A.second) / (A.first - B.first);
}
void replace(stack<pair<llint, llint>> &src, stack<pair<llint, llint>> &dest) {
while (!src.empty()) {
if (dest.size() < 3) {
dest.push(src.top());
src.pop();
continue;
}
pair<llint, llint> A, B, C;
while (dest.size() >= 3) {
B = dest.top(); dest.pop();
A = dest.top();
C = src.top();
if (intersect(A, C) < intersect(B, C))
continue;
dest.push(B);
break;
}
dest.push(C);
src.pop();
}
}
llint ccw(int i, int j, int k) {
return A[i] * (B[j] - B[k]) + A[j] * (B[k] - B[i]) + A[k] * (B[i] - B[j]);
}
void insert(int x, int *t) {
while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), x) > 0)
hull.pop_back();
hull.push_back(x);
if (*t >= hull.size()) *t = max(0, (int) hull.size() - 1);
}
pair<llint, int> dp(llint cost) {
vector<llint> f(n, 0);
vector<int> cnt(n, 0);
hull.clear();
A.resize(n, 0); B.resize(n, 0);
int t = 0;
for (int i = 0; i < n; ++i) {
llint c = (llint) I[i].second * I[i].second + cost;
llint x = (llint) I[i].second;
f[i] = INF;
cnt[i] = -1;
(llint)(I[i].second - I[0].first + 1) * (I[i].second - I[0].first + 1) +
cost;
cnt[i] = 1;
for (; t < (int) hull.size(); ++t) {
llint a = A[hull[t]], b = B[hull[t]];
if (c + a * x + b > f[i]) { --t; break; }
f[i] = c + a * x + b;
cnt[i] = cnt[hull[t]] + 1;
}
t = max(0, t);
t = min((int) hull.size() - 1, t);
llint single =
(llint)(I[i].second - I[0].first + 1) * (I[i].second - I[0].first + 1) +
cost;
if (single < f[i]) {
f[i] = single;
cnt[i] = 1;
}
A[i] = -2LL * (I[i + 1].first - 1);
B[i] = f[i] + (llint)(I[i + 1].first - 1) * (I[i + 1].first - 1) -
(llint)max(0, I[i].second - I[i + 1].first + 1) *
max(0, I[i].second - I[i + 1].first + 1);
insert(i, &t);
}
return {f[n - 1], cnt[n - 1]};
}
llint take_photos(int nn, int mm, int kk, vector<int> r, vector<int> c) {
n = nn; m = mm; k = kk;
for (int i = 0; i < n; ++i) P.emplace_back(r[i], c[i]);
I = get_intervals(n, r, c);
n = (int)I.size();
I.emplace_back(1e9, 1e9);
llint lo = 0, hi = (llint) 2 * m * m;
while (lo < hi) {
llint mid = (lo + hi) / 2;
auto val = dp(mid);
if (val.second > k) lo = mid + 1; else hi = mid;
}
auto sol = dp(lo);
return sol.first - sol.second * lo;
}
컴파일 시 표준 에러 (stderr) 메시지
aliens.cpp: In function 'void insert(int, int*)':
aliens.cpp:93:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (*t >= hull.size()) *t = max(0, (int) hull.size() - 1);
~~~^~~~~~~~~~~~~~
aliens.cpp: In function 'std::pair<long long int, int> dp(llint)':
aliens.cpp:107:80: warning: value computed is not used [-Wunused-value]
(llint)(I[i].second - I[0].first + 1) * (I[i].second - I[0].first + 1) +
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
cost;
~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |