이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sq(ll a) {return a * a;}
struct lichao_tree{
struct node{
pair<ll, ll> line;
int cnt = 0;
int l = -1, r = -1;
node(ll a, ll b, int cnt): line(a, b), cnt(cnt) {}
ll eval(ll x){
return line.first * x + line.second;
}
};
int L, R;
lichao_tree(int lrange, int rrange): L(lrange), R(rrange) {}
vector<node> g;
void insert(ll a, ll b, int cnt){
if (g.size() == 0){
g.emplace_back(a, b, cnt);
return;
}
int tidx = 0;
int tl = L, tr = R;
node tmp(a, b, cnt);
while (true){
int tm = (tl + tr)>>1;
bool left = g[tidx].eval(tl) > tmp.eval(tl);
bool mid = g[tidx].eval(tm) > tmp.eval(tm);
if (mid || (g[tidx].eval(tm) == tmp.eval(tm) && g[tidx].cnt < tmp.cnt)){
swap(g[tidx].line, tmp.line);
swap(g[tidx].cnt, tmp.cnt);
}
if (tl == tr) return;
if (left != mid){
if (g[tidx].l == -1){
g[tidx].l = g.size();
g.emplace_back(tmp);
return;
}
tidx = g[tidx].l;
tr = tm;
}
else{
if (g[tidx].r == -1){
g[tidx].r = g.size();
g.emplace_back(tmp);
return;
}
tidx = g[tidx].r;
tl = tm+1;
}
}
}
pair<ll, int> query(int pos){
pair<ll, int> result(LLONG_MAX, -1);
assert((g.size()));
int tidx = 0;
int tl = L, tr = R;
while (tidx != -1){
result = min(result, make_pair(g[tidx].eval(pos), g[tidx].cnt));
int tm = (tl + tr);
if (pos <= tm){
tidx = g[tidx].l;
tr = tm;
}
else{
tidx = g[tidx].r;
tl = tm+1;
}
}
return result;
}
};
pair<ll, int> alien_solve(const vector<pair<ll, ll>> &p, ll cost){
lichao_tree tree(0, 2000000);
pair<ll, int> result(0, 0);
for (int i=0; i<p.size(); i++){
ll intersect = i ? sq(max(0LL, p[i-1].second - p[i].first + 1)) : 0;
tree.insert(-2 * p[i].first, result.first + sq(p[i].first) - intersect, result.second+1);
result = tree.query(p[i].second + 1);
result.first += sq(p[i].second + 1) + cost;
}
return result;
}
vector<pair<ll, ll>> simplify(vector<pair<ll, ll>> &p){
sort(p.begin(), p.end(), [](const pair<ll, ll> &a, const pair<ll, ll> &b){
return make_pair(a.first, -a.second) < make_pair(b.first, -b.second);
});
vector<pair<ll, ll>> r; r.reserve(p.size());
for (const pair<ll, ll> &a: p){
if (r.size() && a.second <= r.back().second) continue;
r.push_back(a);
}
return r;
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
vector<pair<ll, ll>> p(n);
for (int i=0; i<n; i++)
p[i] = minmax(r[i], c[i]);
p = simplify(p);
ll bl = 0, br = 1e18;
while (bl < br){
ll bm = (bl + br)>>1;
if (alien_solve(p, bm).second > k) bl = bm + 1;
else br = bm;
}
pair<ll, int> result = alien_solve(p, bl);
return result.first - k * bl;
}
컴파일 시 표준 에러 (stderr) 메시지
aliens.cpp: In function 'std::pair<long long int, int> alien_solve(const std::vector<std::pair<long long int, long long int> >&, ll)':
aliens.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i=0; i<p.size(); i++){
| ~^~~~~~~~~
# | 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... |