Submission #555763

#TimeUsernameProblemLanguageResultExecution timeMemory
555763nots0fastAliens (IOI16_aliens)C++17
0 / 100
277 ms49616 KiB
#include "aliens.h" #include <fstream> #include <iostream> #include <math.h> #include <algorithm> using namespace std; #define mp(a,b) make_pair(a,b) #define ff first #define setp setprecision(12)<<fixed #define ss second #define fori(v) for(ll i=0; i<v; i++) #define forj(v) for(ll j=0; j<v; j++) #define fork(v) for(ll k=0; k<v; k++) #define forl(v) for(ll l=0; l<v; l++) #define fort(v) for(ll t=0; t<v; t++) #define forz(v) for(ll z=0; z<v; z++) #define forx(v) for(ll x=0; x<v; x++) #define ll long long #define lll __int128 #define ld long double #define pb(a) push_back(a) // #define cout out // #define cin in ll inf = pow(10, 18); ll modulo = pow(10,9) + 7; double eps = 1e-10; ifstream in; ofstream out; struct line{ ll k, b; ll cnt; line(){} line(ll k1, ll b1, ll cn){ k = k1, b = b1, cnt = cn; } }; ll func(line& cur, ll x){ return cur.k * x + cur.b; } // min number of transitions bool better(line& a, line& b, ll x){ ll vl1 = func(a, x); ll vl2 = func(b, x); if(vl1 < vl2 || ( (vl1 == vl2) && (a.cnt < b.cnt) )){ return 1; } else{ return 0; } } #define MAX 2'100'010 line seg[MAX]; // ql = -inf, qr = inf // O(q * log^2(n)) for range updates void add(ll hd, ll l, ll r, ll ql, ll qr, line cur){ if(qr < l || r < ql){ return; } ll mid = (l+r)/2; if(ql <= l && r <= qr){ // O(log(n)) bool md = better(cur, seg[hd], mid); bool lf = better(cur, seg[hd], l) ; if(md){ swap(seg[hd], cur); } if(l == r){ return; } if(md == lf){ add(2*hd + 1, mid+1, r, ql, qr, cur); } else{ add(2*hd, l, mid, ql, qr, cur); } } else{ add(2*hd + 1, mid+1, r, ql, qr, cur); add(2*hd, l, mid, ql, qr, cur); } } // [l ... r] void que(ll hd, ll l, ll r , ll x, line& best){ if(better(seg[hd], best, x)){ best = seg[hd]; } if(l == r){ return; } ll mid = (l+r)/2; if(x <= mid){ que(hd*2, l, mid, x, best); } else{ que(hd*2+1, mid+1, r, x, best); } } bool J(pair<ll, ll>& a, pair<ll ,ll>& b){ if(a.ff != b.ff){ return a.ff < b.ff; } return a.ss > b.ss; } void calc(vector<pair<ll, ll> >& arr, vector<ll>& dp, vector<ll>& tot, ll& lamda, ll m){ fori(MAX){ seg[i] = line(0, inf, 0); } ll n = arr.size(); dp = vector<ll>(n, inf); tot = vector<ll>(n, inf); dp[0] =0, tot[0] = 0; for(ll i = 1; i<n; i++){ ll li = arr[i].ff, ri = arr[i].ss; ll ri1 = arr[i-1].ss; ll k, b; b = li * li + dp[i-1] - lamda; if(ri1 > li){ b += (ri1 - li) * (ri1 - li); } k = -2*li; add(1, 0, m, 0, m, line(k, b, tot[i-1] + 1)); line best(0, inf, 0); que(1, 0, m, ri, best); dp[i] = func(best, ri) + ri*ri; tot[i] = best.cnt; } } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { m+=10; vector<pair<ll, ll> > arr; fori(n){ if(r[i] > c[i]){ swap(r[i], c[i]); } arr.pb(mp(r[i], c[i])); } sort(arr.begin(), arr.end(), J); ll mxc = -inf; { vector<pair<ll, ll> > good({mp(-inf, -inf)}); fori(n){ ll ri = arr[i].ff, ci = arr[i].ss; if(ci > mxc){ good.pb(mp(ri, ci)); mxc = ci; } } arr = good; } n = arr.size(); for(auto& el : arr){ ++el.ss; } ll lo = -1e12, hi = 0; while(lo < hi){ ll mid = (lo + hi)/2; // has to be closer to high if(hi - mid > mid - lo){ ++mid; } vector<ll> dp, tot; calc(arr, dp, tot, mid, m); if(tot[n-1] > k){ hi = mid-1; } else{ lo = mid; } } vector<ll> dp, tot; calc(arr, dp, tot, lo, m); // cout<<"lamda is "<<lo<<" dp came out "<<dp[n-1]<<endl; // it is definitely k return dp[n-1] - tot[n-1] * lo; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...