oj.uz

Submission #569689

# Submission time Handle Problem Language Result Execution time Memory
569689 2022-05-27T15:52:57 Z Arvin Road Construction (JOI21_road_construction) C++17
0 / 100
 10000 ms 2097152 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll maxA = 1e10;
const int maxN = 250005;

pair<ll, ll> p[maxN], p2[maxN];

struct SegmentTree {
	set<pair<ll, ll>> tree[4*maxN];
	
	void reset(){
		for(int x=0;x<4*maxN;x++){
			tree[x].clear();
		}
	}
	
	void update(int v, int curL, int curR, int pos, ll val1, ll val2){
		if(curL > curR) return;
		if(curL == curR){
			tree[v].insert({val1, val2});
			return;
		}
		
		int curM = (curL+curR) >> 1;
		tree[v].insert({val1, val2});
		
		if(pos <= curM) update(2*v+1, curL, curM, pos, val1, val2);
		else update(2*v+2, curM+1, curR, pos, val1, val2);
	}
	
	void query(int v, int curL, int curR, int l, int r, ll mx, ll cur, vector<ll> &ans){
		if(curL > curR || l > r) return;
		if(curL == l && curR == r){
			for(auto p : tree[v]){
				if(p.first > mx) break;
				ans.push_back(p.second-cur);
			}
			return;
		}
		
		int curM = (curL+curR) >> 1;
		
		query(2*v+1, curL, curM, l, min(curM, r), mx, cur, ans);
		query(2*v+2, curM+1, curR, max(l, curM+1), r, mx, cur, ans);
	}
} tree;

bool customSort(pair<ll, ll> a, pair<ll, ll> b){
	if(a.second == b.second){
		return a.first > b.first;
	}
	return a.second > b.second;
}

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//	freopen("input.txt","r",stdin);
	
	int n, k;
	cin >> n >> k;
	
	for(int x=0;x<n;x++){
		cin >> p[x].first >> p[x].second;
		p2[x] = {p[x].second, -p[x].first};
	}
	
	sort(p, p+n, customSort);
	sort(p2, p2+n, customSort);
	
	vector<ll> vX, vX2;
	for(int x=0;x<n;x++){
		vX.push_back(p[x].first);
		vX2.push_back(p2[x].first);
	}
	
	sort(vX.begin(), vX.end());
	vX.erase(unique(vX.begin(), vX.end()), vX.end());
	
	sort(vX2.begin(), vX2.end());
	vX2.erase(unique(vX2.begin(), vX2.end()), vX2.end());
	
	vector<ll> ans;
	ll max_d = 0;
	{	
		ll left = 1, right = maxA;
		while(left <= right){ // log(N.logN.logMaxA)
			ll mid = (left+right) >> 1;
			
			tree.reset();
			ans.clear();
			
			for(int x=0;x<n;x++){
				int idx = lower_bound(vX.begin(), vX.end(), p[x].first) - vX.begin();
				
				tree.query(0, 0, vX.size()-1, idx+1, vX.size()-1, p[x].first+p[x].second+mid, p[x].first+p[x].second, ans);
				tree.update(0, 0, vX.size()-1, idx, p[x].first+p[x].second, p[x].first+p[x].second);
			}
			
			tree.reset();
			
			for(int x=0;x<n;x++){
				int idx = lower_bound(vX2.begin(), vX2.end(), p2[x].first) - vX2.begin();
				
				tree.query(0, 0, vX2.size()-1, idx+1, vX.size()-1, p2[x].first+p2[x].second+mid, p2[x].first+p2[x].second, ans);
				tree.update(0, 0, vX2.size()-1, idx, p2[x].first+p2[x].second, p2[x].first+p2[x].second);
			}
			
			if(ans.size() >= k){
				max_d = mid;
				right = mid-1;
			} else {
				left = mid+1;
			}
		}
	}
	
	ans.clear();
	
	auto solve = [&](vector<ll> &vX, pair<ll, ll> p[]) -> void {
		tree.reset();
		
		for(int x=0;x<n;x++){
			int idx = lower_bound(vX.begin(), vX.end(), p[x].first) - vX.begin();
			
			tree.query(0, 0, vX.size()-1, idx+1, vX.size()-1, p[x].first+p[x].second+max_d-1, p[x].first+p[x].second, ans);
			tree.update(0, 0, vX.size()-1, idx, p[x].first+p[x].second, p[x].first+p[x].second);
		}
	};
	
	solve(vX, p);
	solve(vX2, p2);
	
	while(ans.size() < k){
		ans.push_back(max_d);
	}
	
	sort(ans.begin(), ans.end());
	
	for(auto val : ans){
		cout << val << "\n";
	}
    return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 54532 KB Output is correct
2 Correct 696 ms 54536 KB Output is correct
3 Correct 628 ms 52408 KB Output is correct
4 Incorrect 602 ms 50224 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 5889 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10075 ms 1130344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10075 ms 1130344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 54532 KB Output is correct
2 Correct 696 ms 54536 KB Output is correct
3 Correct 628 ms 52408 KB Output is correct
4 Incorrect 602 ms 50224 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 54532 KB Output is correct
2 Correct 696 ms 54536 KB Output is correct
3 Correct 628 ms 52408 KB Output is correct
4 Incorrect 602 ms 50224 KB Output isn't correct
5 Halted 0 ms 0 KB -