| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1019221 | Thanhs | 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.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
#define pb push_back
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
#define fi first
#define se second
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l,int r){return l+((hdp()%(r-l+1))+r-l+1)%(r-l+1);}
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int SQ = 450;
const int inf = 1e18;
const int bound = 1e7;
struct line
{
int m = 0, b = inf;
int operator()(int x){return m * x + b;}
};
struct node
{
line ln;
int trace = 0;
node* lc = nullptr;
node* rc = nullptr;
int operator()(int x){return ln(x);}
node(){}
};
node* root = nullptr;
void upd(line nw, int tr, node* cur = root, int l = 0, int r = bound)
{
if (l > r) return;
int m = l + r >> 1;
bool b1 = ((*cur)(l) > nw(l)), b2 = ((*cur)(m) > nw(m));
if(b2)
{
swap(cur -> ln, nw);
swap(cur -> trace, tr);
}
if(b1 != b2)
{
if (! cur -> lc) cur -> lc = new node();
upd(nw, tr, cur -> lc, l, m - 1);
}
else
{
if (! cur -> rc) cur -> rc = new node();
upd(nw, tr, cur -> rc, m + 1, r);
}
}
pair<int, int> query(int x, node* cur = root, int l = 0, int r = bound)
{
if (l > r) return {inf, -1};
int m = l + r >> 1;
pair<int, int> res = {(*cur)(x), cur -> trace};
if (x == m) res;
if(x < m)
{
if (! cur -> lc) return res;
return min(query(x, cur -> lc, l, m - 1), res);
}
else
{
if (! cur -> rc) return res;
return min(query(x, cur -> rc, m + 1, r), res);
}
}
void del(node* cur = root)
{
if(cur -> lc) del(cur -> lc);
if(cur -> rc) del(cur -> rc);
delete(cur);
}
int n;
pair<int, int> C[N];
deque<int> st;
pair<int, int> solve(int x)
{
if(root) del();
root = new node();
upd({- 2 * C[1].fi, - 2 * C[1].fi + C[1].fi * C[1].fi}, 0);
for (int i = 1; i <= n; i++)
{
pair<int,int> res = query(C[i].se);
res.fi += C[i].se * C[i].se + 2 * C[i].se + 1 + x;
res.se++;
if (i == n) return res;
upd({-2 * C[i + 1].fi, res.fi - 2 * C[i + 1].fi + C[i + 1].fi * C[i + 1].fi - max(C[i].fi - C[i + 1].fi + 1, 0ll) * max(C[i].se - C[i + 1].fi + 1, 0ll)}, res.se);
}
}
int take_photos(int32_t _n, int32_t m, int32_t k, int32_t* x, int32_t* y)
{
n = _n;
for (int i = 1; i <= n; i++) {
C[i].fi = x[i - 1];
C[i].se = y[i - 1];
if(C[i].fi > C[i].se) swap(C[i].fi, C[i].se);
}
sort(C + 1, C + 1 + n, [&](pair<int, int> x, pair<int, int> y) {
return make_pair(x.se, x.fi) < make_pair(y.se, y.fi);
});
st.push_back(1);
for (int i = 2; i <= n; i++)
{
while (! st.empty() && C[st.back()].fi >= C[i].fi) st.pop_back();
st.push_back(i);
}
n = 0;
while (!st.empty())
{
C[++n] = C[st.front()];
st.pop_front();
}
int l = -1, r = n * n + 1;
while (l < r - 1)
{
int m = l + r >> 1;
auto res = solve(m);
if (res.se > k) l = m;
else r = m;
}
auto res = solve(r);
return res.fi - res.se * r;
}
// signed main()
// {
// fastIO
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// cin >> n >> m >> k;
// for (int i = 1; i <= n; i++) {
// cin >> C[i].fi >> C[i].se;
// if(C[i].fi > C[i].se) swap(C[i].fi, C[i].se);
// }
// sort(C + 1, C + 1 + n, [&](pair<int, int> x, pair<int, int> y) {
// return make_pair(x.se, x.fi) < make_pair(y.se, y.fi);
// });
// st.push_back(1);
// for (int i = 2; i <= n; i++)
// {
// while (! st.empty() && C[st.back()].fi >= C[i].fi) st.pop_back();
// st.push_back(i);
// }
// n = 0;
// while (!st.empty())
// {
// C[++n] = C[st.front()];
// st.pop_front();
// }
// int l = -1, r = n * n + 1;
// while (l < r - 1)
// {
// int m = l + r >> 1;
// auto res = solve(m);
// if (res.se > k) l = m;
// else r = m;
// }
// auto res = solve(r);
// cout << res.fi - res.se * r;
// }