제출 #907411

#제출 시각아이디문제언어결과실행 시간메모리
907411lightonRoad Construction (JOI21_road_construction)C++17
0 / 100
10089 ms126800 KiB
#include <bits/stdc++.h> #define forf(i,a,b) for(int i = a; i<=b; i++) #define all(v) v.begin(),v.end() #define comp(v) v.erase(unique(all(v)),v.end()) #define LB(i,v) lower_bound(all(v),i)-v.begin() // 1-based #define UB(i,v) upper_bound(all(v),i)-v.begin() #define fi first #define se second using namespace std; typedef long long ll; int N,K; ll X[1000001],Y[1000001]; struct dot{ ll x,y,id; bool operator<(const dot &r) const{ if(x==r.x) return id<r.id; return x<r.x; } } A[1000001]; vector<ll> xl,yl; ll inf = 1e18; ll ab(ll x){ return x<0?-x:x;} struct Node{ int val; int l,r; } def = {0,0,0}; struct PST{ vector<Node> node = {def}; int root[1000001]; void update(int now , int prv, int s, int e, int f, int x){ if(s==e) {node[now].val = node[prv].val + x; return; } int m = s+e>>1; if(f<=m){ node[now].l = node.size(); node[now].r = node[prv].r; node.push_back(def); update(node[now].l,node[prv].l,s,m,f,x); } else{ node[now].r = node.size(); node[now].l = node[prv].l; node.push_back(def); update(node[now].r,node[prv].r,m+1,e,f,x); } node[now].val = node[node[now].l].val+node[node[now].r].val; } int query(int now ,int prv, int s, int e, int l ,int r){ if(l<=s && e<=r) return node[now].val-node[prv].val; if(s>r || e<l) return 0; int m = s+e>>1; return query(node[now].l,node[prv].l,s,m,l,r)+query(node[now].r,node[prv].r,m+1,e,l,r); } } pst; void init(){ forf(i,1,N){ pst.root[i] = pst.node.size(); pst.node.push_back(def); pst.update(pst.root[i],pst.root[i-1],1,N,LB(A[i].y,yl)+1,1); } } ll findmin(ll x, ll y , int count){ ll l = 0; ll r = inf; ll m; while(l+1<r){ m = l+r>>1; int ys = LB(y-m,yl) + 1; int ye = UB(y+m,yl)-1 + 1; int xs = LB(x,xl) + 1; int xe = UB(x+m,xl)-1 + 1; int tmp = pst.query(pst.root[xe],pst.root[xs-1],1,N,ys,ye); if(tmp >= count) r=m; else l=m; } return r; } int cnt[1000001]; void solve(){ init(); priority_queue<pair<ll,int> > pq; forf(i,1,N) cnt[i] = 1; forf(i,1,N){ pq.push({-findmin(X[i],Y[i],cnt[i]+1) , i}); cnt[i]++; } forf(trash,1,K) { printf("%lld\n", -pq.top().first); int i = pq.top().second; pq.pop(); pq.push({-findmin(X[i],Y[i],cnt[i]+1) , i}); cnt[i]++; } } vector<ll> All; void naive(){ forf(i,1,N){ forf(j,i+1,N){ All.push_back(max(ab(X[i]-X[j]),ab(Y[i]-Y[j]))); } } sort(all(All)); forf(i,0,K-1) printf("%lld\n" , All[i]); } int main(){ scanf("%d %d" , &N,&K); forf(i,1,N) scanf("%lld %lld" , &X[i] , &Y[i]); forf(i,1,N){ ll x = X[i], y = Y[i]; X[i] = x+y; Y[i] = x-y; A[i] = {X[i],Y[i],i}; yl.push_back(Y[i]); xl.push_back(X[i]); } sort(all(yl)); comp(yl); sort(all(xl)); sort(A+1,A+N+1); solve(); }

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

road_construction.cpp: In member function 'void PST::update(int, int, int, int, int, int)':
road_construction.cpp:33:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int m = s+e>>1;
      |                 ~^~
road_construction.cpp: In member function 'int PST::query(int, int, int, int, int, int)':
road_construction.cpp:49:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int m = s+e>>1;
      |                 ~^~
road_construction.cpp: In function 'll findmin(ll, ll, int)':
road_construction.cpp:66:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         m = l+r>>1;
      |             ~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     scanf("%d %d" , &N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:111:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     forf(i,1,N) scanf("%lld %lld" , &X[i] , &Y[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...