oj.uz

Submission #391515

# Submission time Handle Problem Language Result Execution time Memory
391515 2021-04-19T06:40:46 Z patrikpavic2 Road Construction (JOI21_road_construction) C++17
100 / 100
 4418 ms 102452 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 58204 KB Output is correct
2 Correct 105 ms 58292 KB Output is correct
3 Correct 99 ms 58264 KB Output is correct
4 Correct 98 ms 58376 KB Output is correct
5 Correct 99 ms 57164 KB Output is correct
6 Correct 46 ms 53640 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2599 ms 94448 KB Output is correct
2 Correct 2574 ms 94376 KB Output is correct
3 Correct 97 ms 58168 KB Output is correct
4 Correct 2380 ms 90600 KB Output is correct
5 Correct 2140 ms 98636 KB Output is correct
6 Correct 2141 ms 98732 KB Output is correct
7 Correct 2181 ms 93216 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3195 ms 91708 KB Output is correct
2 Correct 3179 ms 93052 KB Output is correct
3 Correct 37 ms 53444 KB Output is correct
4 Correct 2017 ms 90604 KB Output is correct
5 Correct 3244 ms 94344 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3195 ms 91708 KB Output is correct
2 Correct 3179 ms 93052 KB Output is correct
3 Correct 37 ms 53444 KB Output is correct
4 Correct 2017 ms 90604 KB Output is correct
5 Correct 3244 ms 94344 KB Output is correct
6 Correct 3449 ms 95156 KB Output is correct
7 Correct 3386 ms 94776 KB Output is correct
8 Correct 37 ms 53452 KB Output is correct
9 Correct 36 ms 53452 KB Output is correct
10 Correct 3180 ms 92444 KB Output is correct
11 Correct 2033 ms 90580 KB Output is correct
12 Correct 3329 ms 94384 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 58204 KB Output is correct
2 Correct 105 ms 58292 KB Output is correct
3 Correct 99 ms 58264 KB Output is correct
4 Correct 98 ms 58376 KB Output is correct
5 Correct 99 ms 57164 KB Output is correct
6 Correct 46 ms 53640 KB Output is correct
7 Correct 1467 ms 75376 KB Output is correct
8 Correct 1585 ms 75368 KB Output is correct
9 Correct 100 ms 58380 KB Output is correct
10 Correct 1403 ms 74248 KB Output is correct
11 Correct 1121 ms 71032 KB Output is correct
12 Correct 1210 ms 71756 KB Output is correct
13 Correct 1219 ms 72324 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 58204 KB Output is correct
2 Correct 105 ms 58292 KB Output is correct
3 Correct 99 ms 58264 KB Output is correct
4 Correct 98 ms 58376 KB Output is correct
5 Correct 99 ms 57164 KB Output is correct
6 Correct 46 ms 53640 KB Output is correct
7 Correct 2599 ms 94448 KB Output is correct
8 Correct 2574 ms 94376 KB Output is correct
9 Correct 97 ms 58168 KB Output is correct
10 Correct 2380 ms 90600 KB Output is correct
11 Correct 2140 ms 98636 KB Output is correct
12 Correct 2141 ms 98732 KB Output is correct
13 Correct 2181 ms 93216 KB Output is correct
14 Correct 3195 ms 91708 KB Output is correct
15 Correct 3179 ms 93052 KB Output is correct
16 Correct 37 ms 53444 KB Output is correct
17 Correct 2017 ms 90604 KB Output is correct
18 Correct 3244 ms 94344 KB Output is correct
19 Correct 3449 ms 95156 KB Output is correct
20 Correct 3386 ms 94776 KB Output is correct
21 Correct 37 ms 53452 KB Output is correct
22 Correct 36 ms 53452 KB Output is correct
23 Correct 3180 ms 92444 KB Output is correct
24 Correct 2033 ms 90580 KB Output is correct
25 Correct 3329 ms 94384 KB Output is correct
26 Correct 1467 ms 75376 KB Output is correct
27 Correct 1585 ms 75368 KB Output is correct
28 Correct 100 ms 58380 KB Output is correct
29 Correct 1403 ms 74248 KB Output is correct
30 Correct 1121 ms 71032 KB Output is correct
31 Correct 1210 ms 71756 KB Output is correct
32 Correct 1219 ms 72324 KB Output is correct
33 Correct 4418 ms 102452 KB Output is correct
34 Correct 4062 ms 102392 KB Output is correct
35 Correct 3526 ms 101652 KB Output is correct
36 Correct 3356 ms 96848 KB Output is correct
37 Correct 3395 ms 96808 KB Output is correct
38 Correct 3319 ms 96468 KB Output is correct