Submission #623040

#	Time	Username	Problem	Language	Result	Execution time	Memory
623040		CSQ31	Road Construction (JOI21_road_construction)	C++17	5 / 100	1985 ms	2097152 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
//consider the case where we only need k smallest from two different set of points
//if can do this in some reasonable time then apply zs bit trick
//+log factor
//need <= log^3 maybe?
//ok two set need log^2(?)
#define all(a) a.begin(),a.end()
#define pb push_back
const int MAXN = 2000000;
int ndcnt = 0;
int t[MAXN],ch[2][MAXN];
vector<ll>glo;
int main()
{
	int n,k;
	cin>>n>>k;
	vector<array<int,2>>p(n);
	vector<int>cy(n),cxy(n);
	for(int i=0;i<n;i++)cin>>p[i][0]>>p[i][1];
	sort(all(p));
	vector<int>crd;
	for(int i=0;i<n;i++)crd.push_back(p[i][1]);
	sort(all(crd));
	crd.resize(unique(all(crd)) - crd.begin());
	for(int i=0;i<n;i++)cy[i] = lower_bound(all(crd),p[i][1]) - crd.begin();
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++){
			ll c = abs(p[i][0]-p[j][0]);
			c+=abs(p[i][1]-p[j][1]);
			glo.pb(c);	
		}
	}
	sort(all(glo));
	for(int i=0;i<k;i++)cout<<glo[i]<<'\n';
}

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