Submission #1072005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072005		TimDee	Road Construction (JOI21_road_construction)	C++17	100 / 100	3234 ms	23360 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define forn(i,n) for(int i=0; i<n; ++i)
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

struct BIT {
	vector<int> t; int n;
	BIT(int n) {
		t.assign(n,0); this->n=n;
	}
	void add(int i, int x) {
		for(;i<n;i|=i+1) t[i]+=x;
	}
	int sum(int r) {
		int q=0;
		for(;r>=0;r=(r&(r+1))-1) q+=t[r];
		return q;
	}
};

void solve() {

	int n,k; cin>>n>>k;
	vector<pi> a(n);
	forn(i,n) cin>>a[i].f>>a[i].s;
	
	vector<pi> f,s;
	forn(i,n) {
		f.pb({a[i].f+a[i].s,i});
	}
	sort(all(f));
	forn(i,n) {
		int j=f[i].s;
		s.pb({a[j].f-a[j].s,i});
	}
	sort(all(s));

	//forn(i,n) cout<<f[i].f<<','<<f[i].s<<" "; cout<<'\n';
	//forn(i,n) cout<<s[i].f<<','<<s[i].s<<" "; cout<<'\n';

	int l=1, r=4e9;
	while (l<r) {
		int m=(l+r+1)>>1;
		int lx=0,rx=0;
		BIT ft(n);
		int z = 0;
		forn(i,n) {
			while (rx<n && s[rx].f<=s[i].f+m) {
				//cout<<"> "<<m<<' '<<i<<": "<<rx<<' '<<s[i].f<<' '<<s[rx].f<<'\n';
				ft.add(s[rx].s,1); ++rx;
			}
			while (s[lx].f < s[i].f-m) {
				ft.add(s[lx].s,-1); ++lx;
			}

			int j = s[i].s;

			int ls=0, rs=n-1;
			while (ls<rs) {
				int ms=(ls+rs)>>1;
				if (f[ms].f < f[j].f-m) ls=ms+1;
				else rs=ms;
			}
			int lq = rs;
			ls=0, rs=n-1;
			while (ls<rs) {
				int ms=(ls+rs+1)>>1;
				if (f[ms].f > f[j].f+m) rs=ms-1;
				else ls=ms;
			}
			int rq = rs;
			//cout<<"! "<<i<<' '<<f[j].s+1<<"  "<<lx<<" "<<rx<<"  "<<lq<<' '<<rq<<' '<<ft.sum(rq)-ft.sum(lq-1)-1<<'\n';

			z+=ft.sum(rq) - ft.sum(lq-1) - 1;
		}
		z>>=1;
		//cout<<"? "<<m<<": "<<z<<'\n';
		if (z >= k) r=m-1;
		else l=m;
	}

	vector<int> ans;
	int m = r;
	
	set<int> st;
	int lx=0,rx=0;

	forn(i,n) {
		while (rx<n && s[rx].f<=s[i].f+m) {
			st.insert(s[rx].s); ++rx;
		}
		while (lx<i) {
			st.erase(s[lx].s); ++lx;
		}

		int j = s[i].s;

		int ls=0, rs=n-1;
		while (ls<rs) {
			int ms=(ls+rs)>>1;
			if (f[ms].f < f[j].f-m) ls=ms+1;
			else rs=ms;
		}
		int lq = rs;
		ls=0, rs=n-1;
		while (ls<rs) {
			int ms=(ls+rs+1)>>1;
			if (f[ms].f > f[j].f+m) rs=ms-1;
			else ls=ms;
		}
		int rq = rs;


		int j1 = f[j].s;
		auto it = st.lower_bound(lq);
		while (it!=st.end()) {
			int jj = *it;
			if (jj>rq) break;
			int j2 = f[jj].s;
			if (j1==j2) {++it; continue;}
			int d = abs(a[j1].f-a[j2].f)+abs(a[j1].s-a[j2].s);
			ans.pb(d);
			++it;
		}
	}
	sort(all(ans));

	while (ans.size()<k) ans.pb(m+1);

	for(auto&x:ans) cout<<x<<'\n';

}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//int t; cin>>t; while (t--)
	solve();
}

Compilation message (stderr)

road_construction.cpp: In function 'void solve()':
road_construction.cpp:135:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  135 |  while (ans.size()<k) ans.pb(m+1);
      |         ~~~~~~~~~~^~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35