oj.uz

Submission #386396

# Submission time Handle Problem Language Result Execution time Memory
386396 2021-04-06T13:55:15 Z MatheusLealV Road Construction (JOI21_road_construction) C++17
100 / 100
 4187 ms 693832 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
#define N 250020
int n, k;
pii w[N];
int bit[N],ans[N];
inline void upd(int x, int v){
	x+=4;
	assert(x>0);
	for(int i = x; i < N; i += (i&-i)) bit[i] += v;
}
inline int qry(int x){
	x+=4;
	assert(x>0);
	int sum = 0;
	for(int i = x;i>0;i-=(i&-i)) sum+=bit[i];
	return sum;
}
vector<ll> compress;
int compy[N], pilhax[N], pilhay[N], pilhaid[N];
deque<int>tree[4*N];
#define m ((a+b)/2)
void updd(int nod, int a, int b, int i, int j,bool add){
	if(add) tree[nod].pb(j);
	else tree[nod].pop_front();
	if(a==b) return;
	if(i <= m) updd(2*nod,a,m,i,j,add);
	else updd(2*nod+1,m+1,b,i,j,add);
}
void get(int nod, int a, int b, int i, int j, vector<int>&curr){
	if(j < a or i > b) return;
	if(i <= a and j >= b){
		for(auto x: tree[nod]){
			curr.pb(x);
		}
		return;
	}
	get(2*nod, a, m, i, j, curr);get(2*nod+1,m+1,b,i,j,curr);
}
inline int check(int mid){
	for(int i = 0; i <= n+10;i++) bit[i]=0;
	int l=0,r=-1, cost=0;
	for(int i=1;i<=n;i++){
		int mn = 1+(lower_bound(compress.begin(), compress.end(), w[i].s-mid)-compress.begin());
		int mx = (upper_bound(compress.begin(), compress.end(), w[i].s+mid)-compress.begin());
		while(l <= r and pilhax[l] < w[i].f-mid){
			upd(pilhay[l], -1);
			l++;
		}
		if(mn <= mx) cost+=qry(mx)-qry(mn-1);
		if(cost>=k)return cost;
		r++;
		pilhax[r] = w[i].f;//({w[i].f, compy[i]});
		pilhay[r] = compy[i];
		upd(compy[i], 1);
	}
	return cost;
}

inline void take(int mid, vector<int>&ans){
	int l=0,r=-1, cost=0;
	for(int i=1;i<=n;i++){
		while(l <= r and pilhax[l] < w[i].f-mid){
			updd(1,1,n,pilhay[l], pilhaid[l], 0);
			l++;
		}
		int mn = 1+(lower_bound(compress.begin(), compress.end(), w[i].s-mid)-compress.begin());
		int mx = (upper_bound(compress.begin(), compress.end(), w[i].s+mid)-compress.begin());
		vector<int>curr;
		get(1,1,n,mn,mx, curr);
		for(auto x: curr){
			int dx = abs(w[i].f - w[x].f), dy = abs(w[i].s - w[x].s);
			ans.pb(max(dx,dy));
		}
		r++;
		pilhax[r] = w[i].f;//({w[i].f, compy[i]});
		pilhay[r] = compy[i];
		pilhaid[r] = i;
		updd(1,1,n,pilhay[r], pilhaid[r], 1);
	}
}
int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>k;
	for(int i = 1, x, y; i <= n; i++){
		cin>>x>>y;
		w[i]={x+y,x-y};
		compress.push_back(x-y);
	}
	sort(w+1,w+n+1);
	sort(compress.begin(), compress.end());
	compress.erase(unique(compress.begin(),compress.end()),compress.end());
	for(int i = 1; i<=n;i++)compy[i] = (upper_bound(compress.begin(), compress.end(), w[i].s)-compress.begin());
	int ini = 0, fim = (int)(4e9), mid, best=-1;
	while(fim>=ini){
		mid=(ini+fim)/2;
		if(check(mid) >= k) best=mid,fim=mid-1;
		else ini=mid+1;
	}
	vector<int> ans;
	int S = check(best - 1);
	for(int i = 0; i < k-S; i++) ans.pb(best);

	take(best-1,ans);

	sort(all(ans));
	for(int i=0;i<sz(ans);i++)cout<<ans[i]<<"\n";
}

Compilation message

road_construction.cpp: In function 'void take(long long int, std::vector<long long int>&)':
road_construction.cpp:77:16: warning: unused variable 'cost' [-Wunused-variable]
   77 |  int l=0,r=-1, cost=0;
      |                ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 678552 KB Output is correct
2 Correct 557 ms 678492 KB Output is correct
3 Correct 542 ms 678716 KB Output is correct
4 Correct 527 ms 678492 KB Output is correct
5 Correct 586 ms 677452 KB Output is correct
6 Correct 533 ms 673772 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1658 ms 692744 KB Output is correct
2 Correct 1668 ms 692696 KB Output is correct
3 Correct 540 ms 678588 KB Output is correct
4 Correct 1543 ms 692624 KB Output is correct
5 Correct 1512 ms 692876 KB Output is correct
6 Correct 1423 ms 692948 KB Output is correct
7 Correct 1391 ms 691940 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2484 ms 689492 KB Output is correct
2 Correct 2662 ms 689752 KB Output is correct
3 Correct 493 ms 673644 KB Output is correct
4 Correct 1219 ms 689500 KB Output is correct
5 Correct 1236 ms 689524 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2484 ms 689492 KB Output is correct
2 Correct 2662 ms 689752 KB Output is correct
3 Correct 493 ms 673644 KB Output is correct
4 Correct 1219 ms 689500 KB Output is correct
5 Correct 1236 ms 689524 KB Output is correct
6 Correct 2865 ms 689556 KB Output is correct
7 Correct 2830 ms 689444 KB Output is correct
8 Correct 491 ms 673772 KB Output is correct
9 Correct 493 ms 673644 KB Output is correct
10 Correct 2881 ms 689416 KB Output is correct
11 Correct 1188 ms 689628 KB Output is correct
12 Correct 1273 ms 689456 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 678552 KB Output is correct
2 Correct 557 ms 678492 KB Output is correct
3 Correct 542 ms 678716 KB Output is correct
4 Correct 527 ms 678492 KB Output is correct
5 Correct 586 ms 677452 KB Output is correct
6 Correct 533 ms 673772 KB Output is correct
7 Correct 1826 ms 684028 KB Output is correct
8 Correct 1827 ms 684092 KB Output is correct
9 Correct 541 ms 678492 KB Output is correct
10 Correct 1512 ms 683524 KB Output is correct
11 Correct 1341 ms 683168 KB Output is correct
12 Correct 1020 ms 684232 KB Output is correct
13 Correct 993 ms 682660 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 678552 KB Output is correct
2 Correct 557 ms 678492 KB Output is correct
3 Correct 542 ms 678716 KB Output is correct
4 Correct 527 ms 678492 KB Output is correct
5 Correct 586 ms 677452 KB Output is correct
6 Correct 533 ms 673772 KB Output is correct
7 Correct 1658 ms 692744 KB Output is correct
8 Correct 1668 ms 692696 KB Output is correct
9 Correct 540 ms 678588 KB Output is correct
10 Correct 1543 ms 692624 KB Output is correct
11 Correct 1512 ms 692876 KB Output is correct
12 Correct 1423 ms 692948 KB Output is correct
13 Correct 1391 ms 691940 KB Output is correct
14 Correct 2484 ms 689492 KB Output is correct
15 Correct 2662 ms 689752 KB Output is correct
16 Correct 493 ms 673644 KB Output is correct
17 Correct 1219 ms 689500 KB Output is correct
18 Correct 1236 ms 689524 KB Output is correct
19 Correct 2865 ms 689556 KB Output is correct
20 Correct 2830 ms 689444 KB Output is correct
21 Correct 491 ms 673772 KB Output is correct
22 Correct 493 ms 673644 KB Output is correct
23 Correct 2881 ms 689416 KB Output is correct
24 Correct 1188 ms 689628 KB Output is correct
25 Correct 1273 ms 689456 KB Output is correct
26 Correct 1826 ms 684028 KB Output is correct
27 Correct 1827 ms 684092 KB Output is correct
28 Correct 541 ms 678492 KB Output is correct
29 Correct 1512 ms 683524 KB Output is correct
30 Correct 1341 ms 683168 KB Output is correct
31 Correct 1020 ms 684232 KB Output is correct
32 Correct 993 ms 682660 KB Output is correct
33 Correct 4187 ms 693432 KB Output is correct
34 Correct 4103 ms 693700 KB Output is correct
35 Correct 3532 ms 692784 KB Output is correct
36 Correct 1382 ms 693524 KB Output is correct
37 Correct 1389 ms 693832 KB Output is correct
38 Correct 1514 ms 693756 KB Output is correct