제출 #907022

#제출 시각아이디문제언어결과실행 시간메모리
907022ibm2006Road Construction (JOI21_road_construction)C++17
27 / 100
3421 ms2097152 KiB
#include<bits/stdc++.h> using namespace std; typedef long long int ll; const ll inf=1e18; ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000]; pair<ll,ll> p[1100000]; vector<ll> seg1[550000],seg2[550000]; vector<ll> tmp,ans,v,u; void add() { ll i; tmp.clear(); tmp.resize(22); fill(tmp.begin(),tmp.end(),inf); // printf("!"); merge(ans.begin(),ans.end(),v.begin(),v.end(),tmp.begin()); // printf("?"); for(i=0;i<k;i++) { ans[i]=tmp[i]; } } void f1(ll x) { tmp.clear(); tmp.resize(22); fill(tmp.begin(),tmp.end(),inf); merge(seg1[x*2].begin(),seg1[x*2].end(),seg1[x*2+1].begin(),seg1[x*2+1].end(),tmp.begin()); ll i; for(i=0;i<k;i++) { seg1[x][i]=tmp[i]; } if(x==1) return; f1(x/2); } void f2(ll x) { tmp.clear(); tmp.resize(22); fill(tmp.begin(),tmp.end(),inf); merge(seg2[x*2].begin(),seg2[x*2].end(),seg2[x*2+1].begin(),seg2[x*2+1].end(),tmp.begin()); ll i; for(i=0;i<k;i++) { seg2[x][i]=tmp[i]; } if(x==1) return; f2(x/2); } vector<ll> g1(ll x,ll y,ll z) { vector<ll> cur; cur.resize(k); fill(cur.begin(),cur.end(),inf); if(y<l||x>r) return cur; if(l<=x&&y<=r) return seg1[z]; vector<ll> v1,v2; v1=g1(x,(x+y)/2,z*2); v2=g1((x+y)/2+1,y,z*2+1); tmp.clear(); tmp.resize(22); fill(tmp.begin(),tmp.end(),inf); merge(v1.begin(),v1.end(),v2.begin(),v2.end(),tmp.begin()); ll u,i; for(i=0;i<k;i++) { cur[i]=tmp[i]; } return cur; } vector<ll> g2(ll x,ll y,ll z) { vector<ll> cur; cur.resize(k); fill(cur.begin(),cur.end(),inf); if(y<l||x>r) return cur; if(l<=x&&y<=r) return seg2[z]; vector<ll> v1,v2; v1=g2(x,(x+y)/2,z*2); v2=g2((x+y)/2+1,y,z*2+1); tmp.clear(); tmp.resize(22); fill(tmp.begin(),tmp.end(),inf); merge(v1.begin(),v1.end(),v2.begin(),v2.end(),tmp.begin()); ll u,i; for(i=0;i<k;i++) { cur[i]=tmp[i]; } return cur; } ll tr(ll x) { return lower_bound(u.begin(),u.end(),x)-u.begin()+1; } int main() { scanf("%lld %lld",&n,&k); ans.resize(k); fill(ans.begin(),ans.end(),inf); for(i=1;i<=n;i++) { scanf("%lld %lld",&x,&y); p[i]={x,y}; u.push_back(y); } sort(u.begin(),u.end()); u.erase(unique(u.begin(),u.end()),u.end()); sort(p+1,p+n+1); // printf("!"); for(i=1;i<=524288;i++) { seg1[i].resize(k); seg2[i].resize(k); fill(seg1[i].begin(),seg1[i].end(),inf); fill(seg2[i].begin(),seg2[i].end(),inf); } for(i=1;i<=n;i++) { // printf("%lld\n",i); x=p[i].first; y=p[i].second; z=tr(y); l=z; r=262144; v=g1(1,262144,1); for(j=0;j<v.size();j++) { v[j]+=x-y; } // printf("?"); add(); // printf("!"); l=1; r=z-1; v=g2(1,262144,1); for(j=0;j<v.size();j++) { v[j]+=x+y; } //printf("@"); add(); seg1[z+262143].push_back(y-x); seg2[z+262143].push_back(-y-x); sort(seg1[z+262143].begin(),seg1[z+262143].end()); seg1[z+262143].erase(--seg1[z+262143].end()); sort(seg2[z+262143].begin(),seg2[z+262143].end()); seg2[z+262143].erase(--seg2[z+262143].end()); f1((z+262143)/2); f2((z+262143)/2); } //printf("\n\n\n\n%lld\n",ans.size()); for(i=0;i<k;i++) { // printf("!"); printf("%lld\n",ans[i]); } }

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

road_construction.cpp: In function 'std::vector<long long int> g1(ll, ll, ll)':
road_construction.cpp:69:8: warning: unused variable 'u' [-Wunused-variable]
   69 |     ll u,i;
      |        ^
road_construction.cpp: In function 'std::vector<long long int> g2(ll, ll, ll)':
road_construction.cpp:92:8: warning: unused variable 'u' [-Wunused-variable]
   92 |     ll u,i;
      |        ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:134:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for(j=0;j<v.size();j++)
      |                 ~^~~~~~~~~
road_construction.cpp:144:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for(j=0;j<v.size();j++)
      |                 ~^~~~~~~~~
road_construction.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     scanf("%lld %lld",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
road_construction.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         scanf("%lld %lld",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
#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...