| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1119175 | epicci23 | 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 "bits/stdc++.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;
const ll N = (ll) 1e6 + 5;
const ll INF = (ll) 1e18 + 5;
const ll INF2 = (ll) 1e9 + 5;
vector<array<ll,2>> v;
struct Line{
ll sl,cn,tag;
Line(ll _a,ll _b, ll _tag){sl = _a, cn = _b, tag = _tag;}
inline ll get_val(ll _x){return _x * sl + cn;}
};
struct LiChao{
vector<Line> seg;
LiChao(ll _m){
seg.resize(4*_m+5);
for(int i = 0 ; i < 4*_m + 5 ; i++) seg[i] = Line(0,-INF,0);
}
void add(ll rt,ll l,ll r,Line u){
ll mid = (l+r)/2;
if(u.get_val(mid) >= seg[rt].get_val(mid)) swap(seg[rt],u);
if(l==r) return;
if(u.sl >= seg[rt].sl) add(rt*2+1,mid+1,r,u);
else add(rt*2,l,mid,u);
}
Line get_max(ll rt,ll l,ll r,ll ind){
if(l == r) return seg[rt];
Line res = seg[rt] , curi = Line(0,-INF,0);
ll mid = (l + r) / 2;
if(ind <= mid) curi = get_max(rt * 2, l, mid, ind);
else curi = get_max(rt * 2 + 1, mid + 1, r, ind);
if(curi.get_val(ind) > res.get_val(ind)) swap(curi,res);
return res;
}
};
array<ll,2> wqs_binary_search(ll lambda){
vector<ll> dp(n+5,INF),Use(n+5,INF);
Use[0] = dp[0] = 0;
LiChao T(N);
Line ekle(-2 * v[1][0], lambda + v[1][0] * v[1][0], 0);
T.add(1,1,N,ekle);
for(int i = 1; i <= sz(v) ; i++){
ll a = v[i][0] , b = v[i][1];
Line Gel = T.get_max(1,1,N,b);
dp[i] = Gel.get_val(b) + b * b;
Use[i] = Gel.tag + 1;
if(i < sz(v)){
Line ekle2(-2*v[i+1][0], lambda + dp[i] + v[i+1][0] * v[i+1][0]
- max(0LL,b - v[i+1][0]) * max(0LL,b - v[i+1][0]), Use[i]);
T.add(1,1,N,ekle2);
}
}
return {dp[sz(v)],Use[sz(v)]};
}
ll take_photos(int _n,int _m,int _k,vector<int> r,vector<int> c){
ll n = _n, m = _m, k = _k;
for(ll i=0;i<n;i++){
ll a=r[i],b=c[i];
if(a>b) swap(a,b);
v.push_back({a,b});
}
sort(all(v));
vector<array<ll,2>> xdd;
xdd.push_back({-1LL,-1LL});
for(ll i=0;i<n;i++){
if(v[i][0] == xdd.back()[0]){
xdd.pop_back();
xdd.push_back(v[i]);
}
else if(xdd.back()[1] < v[i][1]) xdd.push_back(v[i]);
}
swap(v,xdd);
n = sz(v) - 1;
ll res_l = 0, res_r = INF2;
while(res_l < res_r){
ll lol = (res_l+res_r)/2;
array<ll,2> hmm = wqs_binary_search(lol);
if(hmm[1] > k) res_l = lol + 1;
else res_r = lol;
}
array<ll,2> ANS = wqs_binary_search(res_l);
return ANS[0] - res_l * ANS[1];
}
/*void _(){
int n,m,k;
cin >> n >> m >> k;
for(int i=0;i<n;i++){
int a,b;
cin >> a >> b;
if(a>b) swap(a,b);
v.push_back({a,b});
}
ll ans = INF;
sort(all(v));
vector<array<ll,2>> xdd;
xdd.push_back({-1LL,-1LL});
for(int i=0;i<n;i++){
if(v[i][0] == xdd.back()[0]){
xdd.pop_back();
xdd.push_back(v[i]);
}
else if(xdd.back()[1] < v[i][1]) xdd.push_back(v[i]);
}
swap(v,xdd);
n = sz(v) - 1;
dp.assign(n+5,INF);
dp[0] = 0;
for(int i=1;i<=k;i++){
ndp.assign(n+5,INF);
f(1,n,1,n);
swap(dp,ndp);
ans=min(ans,dp[n]);
}
cout << ans << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/