제출 #588272

#제출 시각아이디문제언어결과실행 시간메모리
588272sofapudenAliens (IOI16_aliens)C++14
0 / 100
0 ms212 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll inf = 2e14; const int mxN = 1e5+5; struct line{ ll a, b; int cn; line(ll _a, ll _b, int _cn) : a(_a), b(_b), cn(_cn) {} line(ll _a, ll _b) : line(_a, _b, 0) {} ll eval(ll x){return (x-a+1)*(x-a+1)+b;} }; vector<int> vals; struct LCT{ vector<line> st; LCT(int n) : st(4*n,line(0,inf)) {} void ins(line f, int l, int r, int p){ if(l > r)return; int m = (l+r)>>1; bool lf = st[p].eval(vals[l]) > f.eval(vals[l]); bool mf = st[p].eval(vals[m]) > f.eval(vals[m]); if(mf)swap(st[p],f); if(lf == mf)ins(f,m+1,r,p<<1|1); else ins(f,l,m-1,p<<1); } line que(int x, int l, int r, int p){ int m = (l+r)>>1; if(vals[m] == x)return st[p]; if(vals[m] > x){ line cu = que(x,l,m-1,p<<1); if(st[p].eval(x) < cu.eval(x))return st[p]; else if(st[p].cn < cu.cn)return st[p]; else return cu; } else{ line cu = que(x,m+1,r,p<<1|1); if(st[p].eval(x) < cu.eval(x))return st[p]; else if(st[p].cn < cu.cn)return st[p]; else return cu; } } }; ll take_photos(int N, int M, int k, vector<int> R, vector<int> C) { vector<pair<int,int>> v; for(int i = 0; i < N; ++i){if(R[i] < C[i])swap(R[i],C[i]);v.push_back({R[i],C[i]});} sort(v.begin(),v.end()); for(int i = 0; i < N; ++i)vals.push_back(v[i].first); // dp[n][n][k] current index : start : amount // remove k with alien trick // remove second n with CHT (LiChaoTree) // O(n log^2(n)) ll l = 0, r = inf, ans = 0; while(l <= r){ ll m = (l+r)>>1; LCT lct(N); lct.ins(line(v[0].second,m,1),0,N-1,1); for(int i = 1; i < N; ++i){ line cu = lct.que(v[i-1].first,0,N-1,1); lct.ins(line(v[i].second,m+cu.eval(v[i-1].first)-(v[i-1].first >= v[i].second ? (v[i-1].first-v[i].second+1)*(v[i-1].first-v[i].second) : 0),cu.cn+1),0,N-1,1); } line cu = lct.que(v[N-1].first,0,N-1,1); if(cu.cn > k){ l = m+1; } else{ r = m-1; ans = cu.eval(v[N-1].first)-m*k; } } return ans; }
#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...