oj.uz

Submission #544391

# Submission time Handle Problem Language Result Execution time Memory
544391 2022-04-01T20:27:48 Z ivan_tudor Road Construction (JOI21_road_construction) C++14
100 / 100
 7670 ms 58236 KB 
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;


const int N = 250005;
struct points{
	long long x, y;
	int id;
	bool operator < (points oth) const{
		if(y == oth.y)
			return x < oth.x;
		return y < oth.y;
	}
};

using ordered_set = tree<points, null_type,less<points>, rb_tree_tag,tree_order_statistics_node_update>;

int n;
points v[N];
points vinit[N];
vector<long long> dist;
long long getdst(int i, int j){
	return llabs(vinit[i].x - vinit[j].x) + llabs(vinit[i].y - vinit[j].y);
}
bool cmp(pair<points, bool> a, pair<points, bool> b){
	if(a.first.x == b.first.x){
		return a.second < b.second;
	}
	return a.first.x < b.first.x;
}
long long check(long long dst, bool ok){
  vector<pair<points, bool>> vc;
  for(int i = 1; i <=n; i++){
		vc.push_back({v[i], true});
		vc.push_back({{v[i].x + dst + 1, v[i].y, v[i].id}, false});
  }
  sort(vc.begin(), vc.end(), cmp);
	ordered_set oset;
	long long ans = 0;
	for(auto ev:vc){
		if(ev.second == false){
			ev.first.x -= (dst + 1);
			oset.erase(ev.first);
		}
		else{
			points cur = ev.first;
			if(ok == true){
				auto itrfirst = oset.lower_bound({LLONG_MIN, cur.y - dst});
				auto itrlast = oset.upper_bound({LLONG_MAX, cur.y + dst}); /// e pe urm buna
				while(itrfirst != itrlast){
					points aux = (*itrfirst);
					dist.push_back(getdst(aux.id, cur.id));
					itrfirst++;
				}
			}
			else{
				long long curr = 0;
        curr -= oset.order_of_key({LLONG_MIN, cur.y - dst});
        curr += oset.order_of_key({LLONG_MIN, cur.y + dst + 1});

        ans += curr;
			}
			oset.insert(cur);
		}
  }
  return ans;
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int k;
  cin>>n>>k;
  for(int i = 1; i<=n; i++){
		int x, y;
		cin>>x>>y;
		vinit[i].x = x;
		vinit[i].y = y;

		v[i].x = x + y;
		v[i].y = x - y;
		v[i].id = i;
  }
	long long dst = 0;
	for(long long p2 = (1LL <<(32)); p2; p2>>=1){
		long long cnt = check(dst + p2, false);
		if(cnt < k){
			dst += p2;
		}
	}
	check(dst, true);
	while(dist.size() < k){
		dist.push_back(dst + 1);
	}
	sort(dist.begin(), dist.end());
	for(auto x:dist){
		cout<<x<<"\n";
	}
	return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:96:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |  while(dist.size() < k){
      |        ~~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5200 KB Output is correct
2 Correct 63 ms 5116 KB Output is correct
3 Correct 51 ms 5244 KB Output is correct
4 Correct 51 ms 5164 KB Output is correct
5 Correct 54 ms 4052 KB Output is correct
6 Correct 16 ms 524 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5060 ms 56744 KB Output is correct
2 Correct 5058 ms 56508 KB Output is correct
3 Correct 47 ms 5040 KB Output is correct
4 Correct 5032 ms 56296 KB Output is correct
5 Correct 5490 ms 56408 KB Output is correct
6 Correct 5494 ms 56488 KB Output is correct
7 Correct 5286 ms 56020 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6205 ms 53588 KB Output is correct
2 Correct 6060 ms 53700 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 5352 ms 55232 KB Output is correct
5 Correct 6758 ms 57688 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6205 ms 53588 KB Output is correct
2 Correct 6060 ms 53700 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 5352 ms 55232 KB Output is correct
5 Correct 6758 ms 57688 KB Output is correct
6 Correct 6448 ms 54292 KB Output is correct
7 Correct 6273 ms 53680 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 6189 ms 53580 KB Output is correct
11 Correct 5392 ms 55276 KB Output is correct
12 Correct 6682 ms 57944 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5200 KB Output is correct
2 Correct 63 ms 5116 KB Output is correct
3 Correct 51 ms 5244 KB Output is correct
4 Correct 51 ms 5164 KB Output is correct
5 Correct 54 ms 4052 KB Output is correct
6 Correct 16 ms 524 KB Output is correct
7 Correct 2843 ms 23580 KB Output is correct
8 Correct 2769 ms 23468 KB Output is correct
9 Correct 52 ms 5136 KB Output is correct
10 Correct 2465 ms 23072 KB Output is correct
11 Correct 2195 ms 22924 KB Output is correct
12 Correct 2529 ms 23100 KB Output is correct
13 Correct 2577 ms 23068 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5200 KB Output is correct
2 Correct 63 ms 5116 KB Output is correct
3 Correct 51 ms 5244 KB Output is correct
4 Correct 51 ms 5164 KB Output is correct
5 Correct 54 ms 4052 KB Output is correct
6 Correct 16 ms 524 KB Output is correct
7 Correct 5060 ms 56744 KB Output is correct
8 Correct 5058 ms 56508 KB Output is correct
9 Correct 47 ms 5040 KB Output is correct
10 Correct 5032 ms 56296 KB Output is correct
11 Correct 5490 ms 56408 KB Output is correct
12 Correct 5494 ms 56488 KB Output is correct
13 Correct 5286 ms 56020 KB Output is correct
14 Correct 6205 ms 53588 KB Output is correct
15 Correct 6060 ms 53700 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 5352 ms 55232 KB Output is correct
18 Correct 6758 ms 57688 KB Output is correct
19 Correct 6448 ms 54292 KB Output is correct
20 Correct 6273 ms 53680 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 6189 ms 53580 KB Output is correct
24 Correct 5392 ms 55276 KB Output is correct
25 Correct 6682 ms 57944 KB Output is correct
26 Correct 2843 ms 23580 KB Output is correct
27 Correct 2769 ms 23468 KB Output is correct
28 Correct 52 ms 5136 KB Output is correct
29 Correct 2465 ms 23072 KB Output is correct
30 Correct 2195 ms 22924 KB Output is correct
31 Correct 2529 ms 23100 KB Output is correct
32 Correct 2577 ms 23068 KB Output is correct
33 Correct 7670 ms 53472 KB Output is correct
34 Correct 7659 ms 53992 KB Output is correct
35 Correct 6740 ms 53468 KB Output is correct
36 Correct 7157 ms 53324 KB Output is correct
37 Correct 6794 ms 52352 KB Output is correct
38 Correct 6866 ms 58236 KB Output is correct