제출 #359325

#제출 시각아이디문제언어결과실행 시간메모리
359325junodeveloperAliens (IOI16_aliens)C++17
4 / 100
4 ms384 KiB
#include "aliens.h" #include <bits/stdc++.h> #define fi first #define se second #define sz(x) ((int)x.size()) using namespace std; #ifdef LOCAL #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (__VA_ARGS__) #define cerr if(0)cout #endif template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";} template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA...a){ while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...); } typedef long long ll; struct point { ll r,c; bool operator<(const point& b)const { return r==b.r?c>b.c:r<b.r; } }; // max cht // cht.insert({a,b}) // cht.query(x) struct CHT { struct line { ll first; ll second; ll count; bool operator<(const line& b)const{ if(first==b.first) { if(second==b.second)return count<b.count; return second<b.second; } return first<b.first; } }; using frac=pair<ll,line>; const ll INF=1e18; set<line> ls; set<frac> fs; inline frac getf(line a,line b) { if(b.fi>a.fi) return {(a.se-b.se)/(b.fi-a.fi)-((a.se-b.se)%(b.fi-a.fi)<0),b}; return {(b.se-a.se)/(a.fi-b.fi)-((b.se-a.se)%(a.fi-b.fi)<0),b}; } void clear() { ls.clear();fs.clear(); } void addln(line ln) { auto it=ls.lower_bound(ln); if(it!=ls.end()) { if(it==ls.begin()) fs.erase({-INF,*it}); else fs.erase(getf(*prev(it,1),*it)); fs.insert(getf(ln,*it)); } if(it!=ls.begin()) fs.insert(getf(*prev(it,1),ln)); else fs.insert({-INF,ln}); ls.insert(ln); } set<line>::iterator removeln(set<line>::iterator it) { if(it!=ls.begin()) fs.erase(getf(*prev(it,1),*it)); else fs.erase({-INF,*it}); if(next(it,1)!=ls.end()) { fs.erase(getf(*it,*next(it,1))); if(it!=ls.begin()) fs.insert(getf(*prev(it,1),*next(it,1))); } return ls.erase(it); } inline bool bad(line a,line b,line c) { return getf(b,c)<=getf(a,b); } void insert(line newline) { auto it=ls.lower_bound({newline.fi,-INF,0}); if(it!=ls.end()&&it->fi==newline.fi) { if(it->se<newline.se) it=removeln(it); else return; } if(it!=ls.end()&&it!=ls.begin()&&bad(*prev(it,1),newline,*it)) return; if(it!=ls.begin()) { auto jt=prev(it,1); while(jt!=ls.begin()&&bad(*prev(jt,1),*jt,newline)) { jt=removeln(jt); jt--; } } while(it!=ls.end()&&next(it,1)!=ls.end()&&bad(newline,*it,*next(it,1))) it=removeln(it); addln(newline); } pair<ll,ll> query(ll x) { auto it=fs.lower_bound({x,{-INF,-INF,0}}); if(it==fs.begin()) return {-INF,0}; it--; return {(it->se.fi)*x+(it->se.se),it->se.count}; } }cht; vector<point> v,tmp; int n,m,k; void add(ll a,ll b,ll c) { cht.insert({-a,-b,c}); } pair<ll,ll> query(ll x) { pair<ll,ll> ret=cht.query(x); return {-ret.fi,ret.se}; } pair<ll,ll> f(ll x) { int i; pair<ll,ll> cur,pre; cht.clear(); for(i=0;i<n;i++) { ll a=-2*(v[i].r-1); ll b=(v[i].r-1)*(v[i].r-1)+pre.fi+x; ll c=pre.se; if(i&&v[i-1].c>=v[i].r) { b-=(v[i-1].c-v[i].r+1)*(v[i-1].c-v[i].r+1); } add(a,b,c); pair<ll,ll> r=query(v[i].c); cur={r.fi+v[i].c*v[i].c,r.se+1}; pre=cur; } return cur; } long long take_photos(int n_, int m_, int k_, std::vector<int> r_, std::vector<int> c_) { v.clear();tmp.clear(); n=n_,m=m_,k=k_; int i,j; for(i=0;i<n;i++) { if(r_[i]>c_[i])swap(r_[i],c_[i]); tmp.push_back({r_[i],c_[i]}); } sort(tmp.begin(),tmp.end()); for(i=0,j=-1;i<n;i++) { if(tmp[i].c>j) { j=tmp[i].c; v.push_back(tmp[i]); } } n=sz(v); ll lo=0,hi=1e13; while(lo<hi) { ll mid=(lo+hi)/2; if(f(mid).se>k)lo=mid+1; else hi=mid; } pair<ll,ll> ans=f(lo); return ans.fi-ans.se*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...