제출 #946108

#제출 시각아이디문제언어결과실행 시간메모리
946108salmonRoad Construction (JOI21_road_construction)C++14
100 / 100
7680 ms60752 KiB
#include <bits/stdc++.h> using namespace std; int N,K; vector<pair<long long int,int>> v; long long int X,Y; long long int lst[250100]; const long long int inf = 1e18 / 2 * 2; vector<int> wacter; long long int plop[250100]; vector<pair<int,pair<int,int>>> de; struct node{ int s, m, e; int num; node *l,*r; node(int S, int E){ s = S; e = E; m = (s + e)/2; num = 0; if(s != e){ l = new node(s,m); r = new node(m + 1,e); } } void update(int i, int k){ if(s == e){ num += k; return; } num += k; if(i <= m){ l -> update(i,k); } else{ r -> update(i,k); } } int query(long long int S, long long int E){ if(S <= lst[s] && lst[e] <= E){ return num; } int V = 0; if(S <= lst[m]){ V += l -> query(S,E); } if(lst[m + 1] <= E){ V += r -> query(S,E); } return V; } void banana(long long int S, long long int E){ if(S <= lst[s] && lst[e] <= E && s != e){ if(l -> num > 0) l -> banana(S,E); if(r -> num > 0) r -> banana(S,E); return; } if(s == e ){ if(num > 0) wacter.push_back(s); return; } int V = 0; if(S <= lst[m]){ l -> banana(S,E); } if(lst[m + 1] <= E){ r -> banana(S,E); } } }*root; int main(){ scanf(" %d",&N); scanf(" %d",&K); for(int i = 0; i < N; i++){ scanf(" %lld",&X); scanf(" %lld",&Y); de.push_back({X+Y,{X,Y}}); } sort(de.begin(),de.end()); for(int i = 0; i < N; i++){ int X = de[i].second.first; int Y = de[i].second.second; v.push_back({X - Y,i}); lst[i] = X + Y; plop[i] = X - Y; } v.push_back({1e16,-1}); sort(v.begin(),v.end()); long long int s = 0; long long int e = 5e9; root = new node(0,N-1); while(s != e){ long long int m = (s + e)/2; int num = 0; int it1 = 0; int it2 = 0; for(int i = 0; i < N; i++){ while(v[it1].first + m < v[i].first){ root -> update(v[it1].second,-1); it1++; } while(v[i].first + m >= v[it2].first){ root -> update(v[it2].second,1); it2++; } num += root -> query(lst[v[i].second] - m, lst[v[i].second] + m ) - 1; if(num / 2 >= K) break; } while(it1 != it2){ root -> update(v[it1].second,-1); it1++; } if(num / 2 >= K){ e = m; } else{ s = m + 1; } } map<long long int,int> mep; int it1 = 0; int it2 = 0; int voom = 0; for(int i = 0; i < N; i++){ while(v[i].first + s > v[it2].first){ root -> update(v[it2].second,1); it2++; } while(v[it1].first + s <= v[i].first){ root -> update(v[it1].second,-1); it1++; } root -> banana(lst[v[i].second] - s + 1, lst[v[i].second] + s - 1); for(int j : wacter){ // if(plop[j] - plop[v[i].second] > s) printf("hh %d %d\n",i,j); mep[max(abs(lst[j] - lst[v[i].second]) , abs(plop[j] - plop[v[i].second]) ) ]++; voom++; } wacter.clear(); } voom -= N; assert(voom <= K * 2); vector<long long int> print; mep.erase(0); for(pair<long long int, int> ii : mep){ pair<long long int, int> temp = ii; for(; K > 0 && temp.second > 0; K--, temp.second -= 2){ print.push_back(temp.first); } } while(K > 0){ print.push_back(s); K--; } for(long long int i : print){ printf("%lld\n",i); } } /* 4 1 1000000000 1000000000 -1000000000 -1000000000 1000000000 -1000000000 -1000000000 1000000000 */

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

road_construction.cpp: In member function 'void node::banana(long long int, long long int)':
road_construction.cpp:75:13: warning: unused variable 'V' [-Wunused-variable]
   75 |         int V = 0;
      |             ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
road_construction.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf(" %d",&K);
      |     ~~~~~^~~~~~~~~~
road_construction.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         scanf(" %lld",&X);
      |         ~~~~~^~~~~~~~~~~~
road_construction.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf(" %lld",&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...