Submission #413739

#TimeUsernameProblemLanguageResultExecution timeMemory
413739sabamakuRoad Construction (JOI21_road_construction)C++14
5 / 100
10061 ms176484 KiB
#include<bits/stdc++.h> #define ll long long #define f first #define s second #define pb push_back using namespace std; ll n,k,b[800005],x[800005],y[800005],Nu[800005],Fi[800005],Se[800005]; map<ll,ll>M1,M2; vector<int>beg[800005],er[800005]; vector<long long>A; multiset<pair<ll,int> >st; multiset<pair<ll,int>>::iterator it; void add(int y,int x){ while(y < 750005){ b[y] += x; y += y&-y; } } int sum(int y){ int x = 0; while(y > 0){ x += b[y]; y -= y&-y; } return x; } ll calc(ll t, bool flag){ vector<ll>v,g; M1.clear(); M2.clear(); for(int i=1; i<=3 * n; i++){ beg[i].clear(); er[i].clear(); } for(int i=1; i<=n; i++){ v.pb(x[i] + y[i]); v.pb(x[i] + y[i] + t + 1); g.pb(x[i] - y[i] - t); g.pb(x[i] - y[i]); g.pb(x[i] - y[i] + t); } sort(v.begin() , v.end()); sort(g.begin() , g.end()); int p = 0; for(int i=0; i<v.size(); i++){ if(!i || v[i] != v[i - 1])p++; M1[v[i]] = p; } p = 0; for(int i=0; i<g.size(); i++){ if(!i || g[i] != g[i - 1])p++; M2[g[i]] = p; } vector<pair<ll,ll> >f; for(int i=1; i<=n; i++){ er[M1[x[i] + y[i] + t + 1]].pb(i); beg[M1[x[i] + y[i]]].pb(i); f.pb({x[i] + y[i] , i}); Nu[i] = M2[x[i] - y[i]]; Fi[i] = M2[x[i] - y[i] - t]; Se[i] = M2[x[i] - y[i] + t]; } sort(f.begin() , f.end()); ll ret = 0; for(int i=1; i<=2 * n; i++){ for(auto ind : er[i]){ add(Nu[ind] , -1); if(flag)st.erase(st.find({Nu[ind] , ind})); } for(auto ind : beg[i]){ ret += sum(Se[ind]) - sum(Fi[ind] - 1); if(flag)it = st.lower_bound({Fi[ind] , 0}); if(flag) while(it != st.end() && (*it).f <= Se[ind]){ A.pb(abs(x[ind] - x[(*it).s]) + abs(y[ind] - y[(*it).s])); it++; } add(Nu[ind] , 1); if(flag)st.insert({Nu[ind] , ind}); } } return ret; } int main(){ ios::sync_with_stdio(false); cin >> n >> k; for(int i=1; i<=n; i++){ cin >> x[i] >> y[i]; } ll l=0,r = 4000000000,mid,ans = 0; while(r >= l){ mid = (l + r) / 2; if(calc(mid , 0) >= k){ ans = mid; r = mid - 1; } else{ l = mid + 1; } } calc(ans - 1 , 1); sort(A.begin() , A.end()); for(auto F : A) cout << F << '\n'; for(int i=0; i<k - (int)A.size(); i++) cout << ans << '\n'; return 0; }

Compilation message (stderr)

road_construction.cpp: In function 'long long int calc(long long int, bool)':
road_construction.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0; i<v.size(); i++){
      |                  ~^~~~~~~~~
road_construction.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=0; i<g.size(); i++){
      |                  ~^~~~~~~~~
#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...