| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 139189 | nvmdava | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<pair<ll, ll> > tmp;
vector<ll> L(1, -1), R(1, -1);
int n;
struct Line{
ll x, y, g;
int id;
Line(int _id, ll _x, ll _y, ll _g){
x = _x;
id = _id;
y = _y;
g = _g;
}
ll query(ll xx){
return y - xx * g;
}
ll cross(ll _y, ll _g){
ll dy = _y - y;
ll dg = _g - g;
return dy / dg + 1;
}
};
vector<Line> line;
int cnt[100005];
ll ans[100005];
void calc(ll c){
line.clear();
int it = 0, sz = 0;
line.push_back(Line(0, 0, L[1] * L[1], 2 * L[1]));
for(int i = 1; i <= n; i++){
while(it < sz && line[it + 1].x <= R[i]) it++;
ans[i] = c + R[i] * R[i] + line[it].query(R[i]);
cnt[i] = cnt[line[it].id] + 1;
if(i == n) break;
ll t = max(0, R[i] - L[i + 1]);
ll yy = ans[i] - t * t + L[i + 1] * L[i + 1];
ll gg = 2 * L[i + 1];
while(sz >= 0 && line[sz].cross(yy, gg) <= line[sz].x){
sz--;
line.pop_back();
}
line.push_back(Line(i,
sz == -1 ? 0 : line[sz].cross(yy, gg),
yy,
gg));
sz++;
it = min(it, sz);
}
}
ll take_photos(int n, int qq, int k, std::vector<int> rr, std::vector<int> cc) {
for(int i = 0; i < n; i++){
tmp.push_back({min(rr[i], cc[i]), - 1 - max(rr[i], cc[i])});
}
sort(tmp.begin(), tmp.end());
int mxm = -1;
for(auto& x : tmp){
if(-x.second > mxm){
mxm = -x.second;
L.push_back(x.first);
R.push_back(mxm);
}
}
::n = n = L.size() - 1;
ll l = 0, r = qq * 1LL * qq;
while(l < r){
ll m = (l + r) >> 1;
calc(m);
if(cnt[n] <= k) r = m;
else l = m + 1;
}
calc(r);
return ans[n] - k * r;
}