Submission #391515

#	Time	Username	Problem	Language	Result	Execution time	Memory
391515		patrikpavic2	Road Construction (JOI21_road_construction)	C++17	100 / 100	4418 ms	102452 KiB

road_construction

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
#include <unordered_set>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;

const int N = 250500;
const int OFF = (1 << 20);

int T[3 * N];
int n, q, po_X[N], po_Y[N];
int ind[3 * N], izb[N];
vector < int > TT[2 * OFF];
ll x[N], y[N];

void update(int lo, int hi, int x){	
	hi += 11, lo += 10;
	for(; hi < 3 * N; hi += hi & -hi)
		T[hi] -= x;
	for(; lo < 3 * N ; lo += lo & -lo)
		T[lo] += x;
}


int query(int x){
	int ret = 0;
	x += 10;
	for(; x ; x -= x & -x)
		ret += T[x];
	return ret;
}

void update2(int i, int a, int b, int lo, int hi, int x){	
	if(lo <= a && b <= hi) {
		TT[i].PB(x);
		return;
	}
	if(a > hi || b < lo) return;
	update2(2 * i, a, (a + b) / 2, lo, hi, x);
	update2(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
}

vector < int > ret;

void query2(int x){
	ret.clear();
	for(x = (x + OFF); x ; x /= 2){
		vector < int > nw;
		for(int y : TT[x])
			if(!izb[y])
				ret.PB(y), nw.PB(y);
		TT[x] = nw;
	}
}


vector < pii > swp;

ll labs(ll x){
	return x > 0 ? x : -x;
}

ll get_dis(int i, int j){
	return max(labs(x[i] - x[j]), labs(y[i] - y[j]));
}

bool cmpX(int A, int B){
	return x[A] < x[B];
}

bool cmpY(int A, int B){
	return y[A] < y[B];
}

ll prebroji(ll k){
	swp.clear();
	memset(T, 0, sizeof(T));
	int A = 0, B = 0, C = 0;
	for(;A < n || B < n || C < n;){
		if(A < n && (B == n || x[po_X[A]] - k <= x[po_X[B]]) && (C == n || x[po_X[A]] - k <= x[po_X[C]] + k))
			swp.PB({0, po_X[A]}), A++;
		else if(B < n && (A == n || x[po_X[B]] < x[po_X[A]] - k) && (C == n || x[po_X[B]] <= x[po_X[C]] + k))
			swp.PB({1, po_X[B]}), B++;
		else
			swp.PB({2, po_X[C]}), C++;
	}
	A = 0, B = 0, C = 0; int siz = 0;
	for(;A < n || B < n || C < n;){
		if(A < n && (B == n || y[po_Y[A]] - k <= y[po_Y[B]]) && (C == n || y[po_Y[A]] - k <= y[po_Y[C]] + k))
			ind[3 * po_Y[A]] = siz++, A++;
		else if(B < n && (A == n || y[po_Y[B]] < y[po_Y[A]] - k) && (C == n || y[po_Y[B]] <= y[po_Y[C]] + k))
			ind[3 * po_Y[B] + 1] = siz++, B++;
		else
			ind[3 * po_Y[C] + 2] = siz++, C++;
	}
	ll ret = 0;
	for(pair < int , int > tmp : swp){
		if(tmp.X == 0)
			update(ind[3 * tmp.Y], ind[3 * tmp.Y + 2], 1);
		else if(tmp.X == 1)
			ret += query(ind[3 * tmp.Y + 1]);
		else
			update(ind[3 * tmp.Y], ind[3 * tmp.Y + 2], -1);
	}
	ret = (ret - n) / 2LL;
	return ret;
}

vector < ll > pot;

void pronadi(ll k){
	swp.clear();
	memset(izb, 0, sizeof(izb));
	int A = 0, B = 0, C = 0;
	for(;A < n || B < n || C < n;){
		if(A < n && (B == n || x[po_X[A]] - k <= x[po_X[B]]) && (C == n || x[po_X[A]] - k <= x[po_X[C]] + k))
			swp.PB({0, po_X[A]}), A++;
		else if(B < n && (A == n || x[po_X[B]] < x[po_X[A]] - k) && (C == n || x[po_X[B]] <= x[po_X[C]] + k))
			swp.PB({1, po_X[B]}), B++;
		else
			swp.PB({2, po_X[C]}), C++;
	}
	A = 0, B = 0, C = 0; int siz = 0;
	for(;A < n || B < n || C < n;){
		if(A < n && (B == n || y[po_Y[A]] - k <= y[po_Y[B]]) && (C == n || y[po_Y[A]] - k <= y[po_Y[C]] + k))
			ind[3 * po_Y[A]] = siz++, A++;
		else if(B < n && (A == n || y[po_Y[B]] < y[po_Y[A]] - k) && (C == n || y[po_Y[B]] <= y[po_Y[C]] + k))
			ind[3 * po_Y[B] + 1] = siz++, B++;
		else
			ind[3 * po_Y[C] + 2] = siz++, C++;
	}
	for(pair < int , int > tmp : swp){
		if(tmp.X == 0)
			update2(1, 0, OFF - 1, ind[3 * tmp.Y], ind[3 * tmp.Y + 2], tmp.Y);
		else if(tmp.X == 1){
			query2(ind[3 * tmp.Y + 1]);
			for(int y : ret)
				if(y < tmp.Y)
					pot.PB(get_dis(y, tmp.Y));
		}
		else
			izb[tmp.Y] = 1;
	}
}


int main(){
	scanf("%d%d", &n, &q);
	for(int i = 0;i < n;i++){
		int tx, ty; scanf("%d%d", &tx, &ty);
		x[i] = tx + ty, y[i] = tx - ty;
		po_X[i] = i, po_Y[i] = i;
	}
	sort(po_X, po_X + n, cmpX);
	sort(po_Y, po_Y + n, cmpY);
	ll mks = 0;
	for(int i = 32;i >= 0;i--)
		if(prebroji(mks + (1LL << i)) < q)
			mks += (1LL << i);
	pronadi(mks); sort(pot.begin(), pot.end());
	for(ll x : pot)
		printf("%lld\n", x);
	
	for(int i = 0;i < q - (int)pot.size();i++)
		printf("%lld\n", mks + 1);
	return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  158 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
road_construction.cpp:160:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |   int tx, ty; scanf("%d%d", &tx, &ty);
      |               ~~~~~^~~~~~~~~~~~~~~~~~

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