| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 311844 | aZvezda | Aliens (IOI16_aliens) | C++14 | 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;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e10 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
struct Line {
ll a, b, delta;
ll y(ll x) {return x * a + b;}
Line(ll _a, ll _b, ll _delta) {a = _a; b = _b; delta = _delta;}
Line() {a = 0; b = mod; delta = 0;}
};
struct Node {
Line val;
Node *l, *r;
Node() {l = nullptr; r = nullptr;}
ll y(ll x) {return val.y(x);}
void expand() {
if(!l) {l = new Node(); r = new Node();}
}
};
struct LiChao {
Node root;
void add(Line nw, Node *curr, ll l = -mod, ll r = mod) {
if(l == -mod && r == mod) {
//cout << "Adding " << nw.a << " " << nw.b << " " << nw.delta << endl;
}
ll m = (l + r) / 2;
bool a = nw.y(l) < curr->y(l);
bool b = nw.y(m) < curr->y(m);
if(b) {swap(curr->val, nw);}
if(r - l == 1) {
return;
}
curr->expand();
if(a != b) {
add(nw, curr->l, l, m);
} else {
add(nw, curr->r, m, r);
}
}
Line get(ll x, Node *curr, ll l = -mod, ll r = mod) {
if(curr == nullptr) {return Line();}
ll m = (l + r) / 2;
if(r - l == 1) {
return curr->val;
}
if(x < m) {
auto rec = get(x, curr->l, l, m);
if(curr->y(x) < rec.y(x)) {
return curr->val;
} else {
return rec;
}
} else {
auto rec = get(x, curr->r, l, m);
if(curr->y(x) < rec.y(x)) {
return curr->val;
} else {
return rec;
}
}
}
void clear() {
root = Node();
}
};
const ll MAX_N = 1e5 + 10;
ll n, m, k;
vector<pair<ll, ll> > points;
ll dp[MAX_N], delta[MAX_N];
LiChao tree;
ll calculate(ll del) {
tree.clear();
dp[0] = delta[0] = 0;
tree.add(Line(-2ll * points[1].second, points[1].second * points[1].second, 0), &(tree.root));
for(ll i = 1; i < points.size(); i ++) {
auto best = tree.get(points[i].first, &(tree.root));
//cout << best.a << " " << best.b << " " << best.delta << " " << best.y(points[i].first) << endl;
dp[i] = best.y(points[i].first) + points[i].first * points[i].first + del;
delta[i] = best.delta + 1;
if(i != points.size() - 1) {
tree.add(Line(-2ll * points[i + 1].second, dp[i] - max(points[i].first - points[i + 1].second, 0ll) * max(points[i].first - points[i + 1].second, 0ll) + points[i + 1].second * points[i + 1].second, delta[i]), &(tree.root));
}
//cout << out(dp[i]) << out(delta[i]) << endl;
}
return delta[points.size() - 1];
}
long long take_photos(ll N, ll M, ll K, std::vector<int> r, std::vector<int> c) {
n = N; m = M; k = K;
for(ll i = 0; i < n; i ++) {
if(r[i] < c[i]) {
points.push_back({c[i], -r[i]});
} else {
points.push_back({r[i], -c[i]});
}
}
sort(points.begin(), points.end());
vector<pair<ll, ll> > cpy;
ll mn = mod;
for(ll i = n - 1; i >= 0; i --) {
if(-points[i].second < mn) {
mn = -points[i].second;
cpy.push_back({points[i].first + 1, -points[i].second});
}
}
cpy.push_back({0, 0});
points = cpy;
reverse(points.begin(), points.end());
for(auto it : points) {
//cout << it << endl;
}
ll lft = -mod, rght = mod;
while(lft < rght - 1) {
ll m = (lft + rght) / 2ll;
if(calculate(m) >= k) {
lft = m;
} else {
rght = m;
}
//cout << out(lft) << out(m) << out(rght) << endl << endl;
}
calculate(lft);
return dp[cpy.size() - 1] - min(k, delta[cpy.size() - 1]) * lft;
}