Submission #1083331

#TimeUsernameProblemLanguageResultExecution timeMemory
1083331vjudge1Aliens (IOI16_aliens)C++17
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> #define cir(i,a,b) for(int i=a;i<b;++i) using namespace std; using lint=long long; using lf=long double; // function: f(x)=kx+b class line{ private: lf k,b;int id; public: constexpr auto operator()(lf x) const{ return pair(k*x+b,-id); } line(lf _k=1e12,lf _b=1e12,int _id=0):k(_k),b(_b),id(_id){} }; class segment{ private: vector<line> a; constexpr auto ls(int u){return u*2;} constexpr auto rs(int u){return u*2+1;} auto insert(int u,int l,int r,line f){ const auto g=a[u]; if(f(l)>g(l)&&f(r)>g(r)) return; if(f(l)<g(l)&&f(r)<g(r)) return a[u]=f,void(); if(l==r) return; const auto mid=(l+r)/2; if(f(mid)<g(mid)){ a[u]=f; if(f(l)>g(l)) insert(ls(u),l,mid,g); else insert(rs(u),mid+1,r,g); }else{ if(f(l)>g(l)) insert(rs(u),mid+1,r,f); else insert(ls(u),l,mid,f); } } auto query(int u,int l,int r,int p){ if(l==r) return a[u](p); const auto mid=(l+r)/2; return min(a[u](p),p-1<mid?query(ls(u),l,mid,p):query(rs(u),mid+1,r,p)); } int n; public: auto insert(line f){insert(1,0,n-1,f);} auto query(int p){return query(1,0,n-1,p);} segment(int _n):n(_n),a(_n<<2,line(1e12,1e12,0)){} }; struct seg{ lint l,r; seg(lint _l,lint _r):l(_l),r(_r){} seg()=default; }; int main(){ ios::sync_with_stdio(false),cin.tie(0); int n,m,k;cin>>n>>m>>k; vector<seg> a(n); for(auto&[l,r]:a){ lint x,y;cin>>x>>y; tie(l,r)=minmax(x,y); } sort(a.begin(),a.end(),[](auto&a,auto&b){ return a.l==b.l?a.r>b.r:a.l<b.l; }); constexpr auto sqr=[&](auto x){return x*x;}; [&](){ const auto na=a; auto cmxr=-1; a.clear(); for(auto&[l,r]:na){ if(r<cmxr+1) continue; a.emplace_back(l,(cmxr=r)); } n=a.size(); }(); auto l=-1e12l,r=1e12l,ans=-1.0l; cir(i,0,60){ const auto mid=(l+r)/2; const auto[w,c]=[&](){ vector<lf> f(n),c(n); segment sg(m+7); sg.insert(line(-a[0].l*2,sqr(a[0].l),0)); cir(i,0,n){ const auto[fx,cnt]=sg.query(a[i].r+1); f[i]=fx+sqr(a[i].r+1)+mid; c[i]=-cnt+1; // cerr<<i<<' '<<f[i]<<' '<<c[i]<<' '<<line(-a[i+1].l,f[i]-sqr(max(a[i].r-a[i+1].l+1,0ll))+sqr(a[i+1].l),cnt+1)(6).first<<'\n'; // cerr<<"qwq\n"; if(i+1<n) sg.insert(line(-a[i+1].l*2,f[i]-sqr(max(a[i].r-a[i+1].l+1,0ll))+sqr(a[i+1].l),cnt+1)); } return pair(f[n-1],c[n-1]); }(); ans=w-min<lint>(c,k)*mid; c>k-1?(r=mid):(l=mid); } cout<<(lint)(round(ans))<<'\n'; return 0; }

Compilation message (stderr)

aliens.cpp: In constructor 'segment::segment(int)':
aliens.cpp:41:9: warning: 'segment::n' will be initialized after [-Wreorder]
   41 |     int n;
      |         ^
aliens.cpp:18:18: warning:   'std::vector<line> segment::a' [-Wreorder]
   18 |     vector<line> a;
      |                  ^
aliens.cpp:45:5: warning:   when initialized here [-Wreorder]
   45 |     segment(int _n):n(_n),a(_n<<2,line(1e12,1e12,0)){}
      |     ^~~~~~~
/usr/bin/ld: /tmp/ccUCX6ra.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cczOblm9.o:aliens.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccUCX6ra.o: in function `main':
grader.cpp:(.text.startup+0xf0): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status