제출 #824933

#제출 시각아이디문제언어결과실행 시간메모리
824933vnm06Aliens (IOI16_aliens)C++14
100 / 100
101 ms9008 KiB
#include "aliens.h" #include<bits/stdc++.h> using namespace std; struct line { long long res, cf, tm; long long brp; line() {} line(long long a, long long b, long long c, long long d) { res=a; cf=b; tm=c; brp=d; } }; long long N; pair<long long, long long> pr[100005]; long long id=0; long long T, ans, totbr; vector<line> lines; void add_line(long long k) { long long res, br, tm, cf; while(id!=lines.size()-1 && lines[id+1].tm<=pr[k].second) id++; res=lines[id].res+(pr[k].second-lines[id].cf+1)*(pr[k].second-lines[id].cf+1)+T; br=lines[id].brp+1; if(k==N-1) { ans=res; totbr=br; } else { cf=pr[k+1].first; if(cf<=pr[k].second) res-=(pr[k].second-cf+1)*(pr[k].second-cf+1); long long tN=lines.size(); while(tN>id) { long long vr=lines[tN-1].tm, res2=lines[tN-1].res, cf2=lines[tN-1].cf; if((vr-cf+1)*(vr-cf+1)+res<=(vr-cf2+1)*(vr-cf2+1)+res2) tN--; else break; } lines.resize(tN); if(tN==id) lines.push_back(line(res, cf, -1, br)); else { long long vr=lines[tN-1].tm, res2=lines[tN-1].res, cf2=lines[tN-1].cf, tm; tm=(res+(cf-1)*(cf-1)-(cf2-1)*(cf2-1)-res2)/(2*cf-2*cf2); if((res+(cf-1)*(cf-1)-(cf2-1)*(cf2-1)-res2)%(2*cf-2*cf2)) tm++; lines.push_back(line(res, cf, tm, br)); } } } pair<long long, long long> solve() { id=0; lines.resize(0); lines.push_back(line(0, pr[0].first, -1, 0)); for(long long i=0; i<N; i++) add_line(i); ///cout<<lines[lines.size()-1].res<<' '<<lines[lines.size()-1].cf<<" "<<lines[lines.size()-1].brp<<endl;} return {totbr, ans}; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { N=n; for(int i=0; i<n; i++) if(r[i]>c[i]) swap(r[i], c[i]); for(int i=0; i<n; i++) pr[i]={r[i], c[i]}; sort(pr, pr+N); long long id=0; for(long long i=1; i<N; i++) { if(pr[i].second<=pr[id].second) continue; if(pr[i].first!=pr[id].first) id++; swap(pr[id], pr[i]); } N=n=id+1; k=min(k, n); ///for(long long i=0; i<n; i++) cout<<pr[i].first<<" "<<pr[i].second<<endl; long long le=0, ri=1e12; while(ri-le>1) { long long mid=(le+ri)/2; T=mid; pair<long long, long long> pr=solve(); ///cout<<T<<" "<<pr.second<<" "<<pr.first<<endl; if(pr.first==k) return pr.second-mid*k; else if(pr.first<k) ri=mid; else le=mid; } T=le; pair<long long, long long> pr=solve(); return pr.second-T*k; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'void add_line(long long int)':
aliens.cpp:29:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(id!=lines.size()-1 && lines[id+1].tm<=pr[k].second) id++;
      |           ~~^~~~~~~~~~~~~~~~
aliens.cpp:53:23: warning: unused variable 'vr' [-Wunused-variable]
   53 |             long long vr=lines[tN-1].tm, res2=lines[tN-1].res, cf2=lines[tN-1].cf, tm;
      |                       ^~
aliens.cpp:28:24: warning: unused variable 'tm' [-Wunused-variable]
   28 |     long long res, br, tm, cf;
      |                        ^~
#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...