Submission #440204

#TimeUsernameProblemLanguageResultExecution timeMemory
440204cheetoseRoad Construction (JOI21_road_construction)C++17
100 / 100
5710 ms36104 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define X first #define Y second #define y0 y12 #define y1 y22 #define INF 987654321987654321 #define PI 3.141592653589793238462643383279502884 #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c)) #define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c)) #define MEM0(a) memset((a),0,sizeof(a)) #define MEM_1(a) memset((a),-1,sizeof(a)) #define ALL(a) a.begin(),a.end() #define COMPRESS(a) sort(ALL(a));a.resize(unique(ALL(a))-a.begin()) #define SYNC ios_base::sync_with_stdio(false);cin.tie(0) using namespace std; typedef long long ll; typedef long double ld; typedef double db; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int, int> Pi; typedef pair<ll, ll> Pll; typedef pair<ld, ld> Pd; typedef vector<int> Vi; typedef vector<ll> Vll; typedef vector<ld> Vd; typedef vector<Pi> VPi; typedef vector<Pll> VPll; typedef vector<Pd> VPd; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef tuple<ll, ll, ll> LLL; typedef vector<iii> Viii; typedef vector<LLL> VLLL; typedef complex<double> base; const int MOD = 998244353; ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; } int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 }; int ddx[] = { -1,-2,1,-2,2,-1,2,1 }, ddy[] = { -2,-1,-2,1,-1,2,1,2 }; int x[250005],y[250005]; Vi v[250005]; Vll vx,vy; int N,M; int n,k; int tree[250005]; void upd(int i, int k){ i++; while (i <= n){ tree[i] += k; i += (i&-i); } } int sum(int i){ int c = 0; i++; while (i > 0){ c += tree[i]; i -= (i&-i); } return c; } bool ok(ll m){ MEM0(tree); ll res=0; int t=0; fup(i,0,N-1,1){ ll x=vx[i]; while(vx[t]<x-m){ for(int j:v[t])upd(j,-1); t++; } for(int j:v[i]){ ll y=vy[j]; res+=sum(upper_bound(ALL(vy),y+m)-vy.begin()-1)-sum(lower_bound(ALL(vy),y-m)-vy.begin()-1); upd(j,1); } } return res>=k; } Vll ans; list<int> lst[250005]; set<int> S; void go(ll m){ int t=0; fup(i,0,N-1,1){ ll x=vx[i]; while(vx[t]<x-m){ for(int j:v[t]){ lst[j].pop_front(); if(lst[j].empty())S.erase(j); } t++; } for(int j:v[i]){ ll y=vy[j]; int L=lower_bound(ALL(vy),y-m)-vy.begin(),R=upper_bound(ALL(vy),y+m)-vy.begin()-1; auto it=S.lower_bound(L); while(it!=S.end() && *it<=R){ int jj=*it; for(int ii:lst[jj]){ ll DX=abs(vx[ii]-vx[i]),DY=abs(vy[jj]-vy[j]); ans.pb(max(DX,DY)); } it++; } lst[j].push_back(i); if(lst[j].size()==1)S.insert(j); } } } int main(){ scanf("%d%d",&n,&k); Vi vv; fup(i,0,n-1,1){ int a,b; scanf("%d%d",&a,&b); x[i]=a+b,y[i]=a-b; vx.pb(x[i]),vy.pb(y[i]); } COMPRESS(vx);COMPRESS(vy); fup(i,0,n-1,1){ v[lower_bound(ALL(vx),x[i])-vx.begin()].pb(lower_bound(ALL(vy),y[i])-vy.begin()); } N=vx.size(),M=vy.size(); ll l=1,r=4e9; while(l<=r){ ll m=l+r>>1; if(ok(m))r=m-1; else l=m+1; } go(l-1); sort(ALL(ans)); for(ll x:ans)printf("%lld\n",x); int c=k-(int)ans.size(); while(c--)printf("%lld\n",l); }

Compilation message (stderr)

road_construction.cpp: In function 'bool ok(ll)':
road_construction.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
road_construction.cpp:70:2: note: in expansion of macro 'fup'
   70 |  fup(i,0,N-1,1){
      |  ^~~
road_construction.cpp: In function 'void go(ll)':
road_construction.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
road_construction.cpp:89:2: note: in expansion of macro 'fup'
   89 |  fup(i,0,N-1,1){
      |  ^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
road_construction.cpp:118:2: note: in expansion of macro 'fup'
  118 |  fup(i,0,n-1,1){
      |  ^~~
road_construction.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
road_construction.cpp:125:2: note: in expansion of macro 'fup'
  125 |  fup(i,0,n-1,1){
      |  ^~~
road_construction.cpp:131:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |   ll m=l+r>>1;
      |        ~^~
road_construction.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
road_construction.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~
#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...