Submission #701220

#	Time	Username	Problem	Language	Result	Execution time	Memory
701220		minhcool	Road Construction (JOI21_road_construction)	C++17	32 / 100	10102 ms	830888 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 250005 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, k;
 
ii a[N], b[N];
 
int savee[N];
 
map<ii, int> mp;
// type1[id]: (-x - y), type2[id]: (-x + y)
 
vector<int> x, y;
vector<int> type1[524290], type2[524290];
vector<int> bit1[524290], bit2[524290];
int mini1[524290], mini2[524290];
 
 
void build(int id, int l, int r){
	bit1[id].resize(r - l + 2), bit2[id].resize(r - l + 2);
	if(l == r){
		type1[id].pb(-b[l].fi - b[l].se);
		type2[id].pb(-b[l].fi + b[l].se);
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	for(auto it : type1[id << 1]) type1[id].pb(it);
	for(auto it : type2[id << 1]) type2[id].pb(it);
	for(auto it : type1[id << 1 | 1]) type1[id].pb(it);
	for(auto it : type2[id << 1 | 1]) type2[id].pb(it);
	sort(type1[id].begin(), type1[id].end());
	sort(type2[id].begin(), type2[id].end());
	type1[id].resize(unique(type1[id].begin(), type1[id].end()) - type1[id].begin());
	type2[id].resize(unique(type2[id].begin(), type2[id].end()) - type2[id].begin());
	bit1[id].resize(type1[id].size() + 1);
	bit2[id].resize(type2[id].size() + 1);
}
 
void upd1(int id, int id2){
	for(; id2 < bit1[id].size(); id2 += id2 & -id2) bit1[id][id2]++;
}
 
int get1(int id, int id2){
	int ans = 0;
	for(; id2; id2 -= id2 & -id2){
		ans += bit1[id][id2];
	}
	return ans;
}
 
void upd2(int id, int id2){
	for(; id2 < bit2[id].size(); id2 += id2 & -id2) bit2[id][id2]++;
}
 
int get2(int id, int id2){
	int ans = 0;
	for(; id2; id2 -= id2 & -id2){
		ans += bit2[id][id2];
	}
	return ans;
}
 
int cnt;
ii point;
 
vector<ii> u1[N], u2[N];
 
void prep(int id, int l, int r, int pos){
	int posi = lower_bound(type1[id].begin(), type1[id].end(), -point.fi - point.se) - type1[id].begin();
	u1[cnt].pb({id, posi});
	posi = lower_bound(type2[id].begin(), type2[id].end(), -point.fi + point.se) - type2[id].begin();
	u2[cnt].pb({id, posi});
	//upd1(id, posi);
	//upd2(id, posi);
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(pos <= mid) prep(id << 1, l, mid, pos);
	else prep(id << 1 | 1, mid + 1, r, pos);
}
 
/*
void upd(int id, int l, int r, int pos){
	//int posi = lower_bound(type1[id].begin(), type1[id].end(), -point.fi - point.se) - type1[id].begin();
	//int posi = 1;
	upd1(id, posi);
	//posi = lower_bound(type2[id].begin(), type2[id].end(), -point.fi + point.se) - type2[id].begin();
	upd2(id, posi);
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(pos <= mid) upd(id << 1, l, mid, pos);
	else upd(id << 1 | 1, mid + 1, r, pos);
}*/
 
int type, val;
 
vector<int> g1[N], g2[N];
vector<int> min_val1[524290], min_val2[524290];
int itr1[524290], itr2[524290];
 
void prep2(int id, int l, int r, int L, int R){// <= val, return no of pairs
	if(l > R || r < L) return;
	if(l >= L && r <= R){
		if(!type){
			g1[cnt].pb(id);
			min_val1[id].pb(a[cnt].fi + a[cnt].se);
		}
		else{
			g2[cnt].pb(id);
			min_val2[id].pb(a[cnt].fi - a[cnt].se);
		}
		return;
	}
	int mid = (l + r) >> 1;
	prep2(id << 1, l, mid, L, R);
	prep2(id << 1 | 1, mid + 1, r, L, R);
}
 
bool cmp(ii a, ii b){
	return a.se < b.se;
}
 
priority_queue<int, vector<int>, greater<int>> pq;
 
int find_mn1(int id, int value){
	int answer = 0;
	for(int i = 19; i >= 0; i--){
		if((answer + (1LL << i)) >= bit1[id].size()) continue;
		if(value > bit1[id][answer + (1LL << i)]){
			value -= bit1[id][answer + (1LL << i)];
			answer += (1LL << i);
		}
	}
	return answer + 1;
}
 
int find_mn2(int id, int value){
	int answer = 0;
	for(int i = 19; i >= 0; i--){
		if((answer + (1LL << i)) >= bit2[id].size()) continue;
		if(value > bit2[id][answer + (1LL << i)]){
			value -= bit2[id][answer + (1LL << i)];
			answer += (1LL << i);
		}
	}
	return answer + 1;
}
 
int pluss;
 
void gett(int id, int l, int r, int L, int R){
	if(l > R || r < L) return;
	if(l >= L && r <= R){
		if(!type){
			int pos = upper_bound(type1[id].begin(), type1[id].end(), val) - type1[id].begin();
			pos--;
			int tempo = get1(id, pos);
			//cout << tempo << "\n";
			//return;
			for(int i = 1; i <= tempo; i++){
				int posi = find_mn1(id, i);
				//continue;
			//	cout << "OKAY " << type1[id][posi] << " " << plus << "\n";
				pq.push(type1[id][posi] + pluss);
			}
			return;
			//return get1(id, pos);
		}
		else{
			int pos = upper_bound(type2[id].begin(), type2[id].end(), val) - type2[id].begin();
			pos--;
			int tempo = get2(id, pos);
			//return;
			for(int i = 1; i <= tempo; i++){
				int posi = find_mn2(id, i);
				assert(posi < type2[id].size());
			//	cout << "OKAY " << type1[id][posi] << " " << plus << "\n";
				pq.push(type2[id][posi] + pluss);
			}
			return;
			//return get2(id, pos);
		}
	}
	int mid = (l + r) >> 1;
	gett(id << 1, l, mid, L, R);
	gett(id << 1 | 1, mid + 1, r, L, R);
}
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
void process(){
	cin >> n >> k;
	/*
	n = k = 130000;
	set<ii> se;
	while(se.size() < n) se.insert({rnd(-1e9, 1e9), rnd(-1e9, 1e9)});
	int cntt = 0;
	for(auto it : se){
	    cntt++;
	    a[cntt] = it;
	}*/
	for(int i = 1; i <= n; i++){
		cin >> a[i].fi >> a[i].se;
		b[i] = a[i];
		x.pb(a[i].fi), y.pb(a[i].se);
	}
	sort(x.begin(), x.end()), sort(y.begin(), y.end());
	x.resize(unique(x.begin(), x.end()) - x.begin());
	y.resize(unique(y.begin(), y.end()) - y.begin());
	sort(a + 1, a + n + 1);
	sort(b + 1, b + n + 1, cmp);
	for(int i = 1; i <= n; i++) mp[b[i]] = i;
	build(1, 1, n);
	//return;
	for(int i = 1; i <= 524288; i++){
		type1[i].pb(-oo), type2[i].pb(-oo);
		sort(type1[i].begin(), type1[i].end());
		sort(type2[i].begin(), type2[i].end());
	}
	//return;
	int l = 1, r = 4e9 + 5;
	int itr = 0;
	for(int i = 1; i <= n; i++) savee[i] = mp[a[i]];
	for(int i = 1; i <= n; i++){
		cnt++;
		point = a[i];
		prep(1, 1, n, savee[i]);
		type = 0;
		prep2(1, 1, n, 1, savee[i]);
		type = 1;
		prep2(1, 1, n, savee[i] + 1, n);
	}
	for(int i = 1; i <= 524288; i++){
		//min_val1[i] = oo, min_val2[i] = oo;
		reverse(min_val1[i].begin(), min_val1[i].end());
		reverse(min_val2[i].begin(), min_val2[i].end());
		int mini = oo;
		for(int j = 0; j < min_val1[i].size(); j++){
		    mini = min(mini, min_val1[i][j]);
		    min_val1[i][j] = mini;
		}
		mini = oo;
		for(int j = 0; j < min_val2[i].size(); j++){
		    mini = min(mini, min_val2[i][j]);
		    min_val2[i][j] = mini;
		}
	}
	int tol_size = 0;
	for(int i = 1; i <= 524288; i++){
	    tol_size += min_val1[i].size();
	    tol_size += min_val2[i].size();
	}
	//cout << tol_size << "\n";
	int cnttt = 0, cnttt2 = 0;
		for(int i = 1; i <= 524288; i++){
			for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
			for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
			mini1[i] = mini2[i] = oo;
			itr1[i] = (int)min_val1[i].size() - 1;
			itr2[i] = (int)min_val2[i].size() - 1;
		}
	while(l < r){
		int mid = (l + r) >> 1;
			/*
			min_val3[i].resize(min_val1[i].size());
			for(int j = 0; j < min_val1[i].size(); j++) min_val3[i][j] = min_val1[i][j];
			min_val4[i].resize(min_val2[i].size());
			for(int j = 0; j < min_val2[i].size(); j++) min_val4[i][j] = min_val2[i][j];*/
			//min_val4[i] = min_val2[i];
		//}
		int answer = 0, total = 0;
		vector<ii> vc1, vc2;
		//unordered_set<int> vc3, vc4;
		for(int i = 1; i <= n; i++){
			int pos = savee[i];
		//	cout << pos << " ";
			val = mid - a[i].fi - a[i].se;
			//answer += get(1, 1, n, 1, pos);
			for(auto it : g1[i]){
			    vc1.pb({it, 0});
			    itr1[it]--;
			    //min_val3[it].pop_back();
				if(mini1[it] == oo || type1[it][mini1[it]] > val) continue;
				cnttt2++;
				int pos = upper_bound(type1[it].begin(), type1[it].end(), val) - type1[it].begin();
				pos--;
				assert(mini1[it] == oo || pos >= mini1[it]);
				//cout << i << " " << it << " " << val << " " << pos << " " << mini1[it] << " " << get1(it, pos) << "\n";
				//assert(get1(it, pos) > 0);
				//cout << "OK " << id << " " << pos << " " << type1[id].size() << "\n";
				answer += get1(it, pos);
				if(answer >= k) break;
			}
			val = mid - a[i].fi + a[i].se;
			for(auto it : g2[i]){
			    vc2.pb({it, 0});
			    itr2[it]--;
			    //min_val4[it].pop_back();
				if(mini2[it] == oo || type2[it][mini2[it]] > val) continue;
				cnttt2++;
				int pos = upper_bound(type2[it].begin(), type2[it].end(), val) - type2[it].begin();
				pos--;
				//assert(get2(it, pos) > 0);
				//cout << "OK " << id << " " << pos << " " << type2[id].size() << "\n";
				answer += get2(it, pos);
				if(answer >= k) break;
			}
			//answer += get(1, 1, n, pos + 1, n);
			//continue;
			//cout << answer << "\n";
			//point = a[i];
			if(answer >= k) break;
			for(auto it : u1[i]){
				if(itr1[it.fi] < 0 || (min_val1[it.fi][itr1[it.fi]] - a[i].fi - a[i].se) > mid) continue;
				total++;
				vc1.pb(it);
				upd1(it.fi, it.se);
				mini1[it.fi] = min(mini1[it.fi], it.se);
				cnttt++;
				if(total >= k) break;
			}
			for(auto it : u2[i]){
				if(itr2[it.fi] < 0 || (min_val2[it.fi][itr2[it.fi]] - a[i].fi + a[i].se) > mid) continue;
				total++;
				vc2.pb(it);
				upd2(it.fi, it.se);
				mini2[it.fi] = min(mini2[it.fi], it.se);
				cnttt++;
				if(total >= k) break;
			}
			if(total >= k){
			    answer = k;
			    break;
			}
			//upd(1, 1, n, pos);
		}
		for(auto it : vc1){
		    //assert(it.se > 0);
		    if(it.se) for(int j = it.se; j < bit1[it.fi].size(); j += j & -j) bit1[it.fi][j] = 0;
		    //for(int j = 0; j < bit1[i.].size(); j++) bit1[i][j] = 0;
		    mini1[it.fi] = oo;
		    itr1[it.fi] = (int)min_val1[it.fi].size() - 1;
		}
		for(auto it : vc2){
		    //assert(it.se > 0);
		    if(it.se) for(int j = it.se; j < bit2[it.fi].size(); j += j & -j) bit2[it.fi][j] = 0;
		    //for(int j = 0; j < bit1[i.].size(); j++) bit1[i][j] = 0;
		    mini2[it.fi] = oo;
		    itr2[it.fi] = (int)min_val2[it.fi].size() - 1;
		}
		/*
		for(int i = 1; i <= 524288; i++){
			for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
			for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
			mini1[i] = mini2[i] = oo;
			itr1[i] = (int)min_val1[i].size() - 1;
			itr2[i] = (int)min_val2[i].size() - 1;
		}*/
			/*
			min_val3[i].resize(min_val1[i].size());
			for(int j = 0; j < min_val1[i].size(); j++) min_val3[i][j] = min_val1[i][j];
			min_val4[i].resize(min_val2[i].size());
			for(int j = 0; j < min_val2[i].size(); j++) min_val4[i][j] = min_val2[i][j];*/
			//min_val4[i] = min_val2[i];
		//}
		//cout << mid << " " << total << " " << answer << "\n";
		//return;
		//cout << mid << " " << answer << "\n";
		if(answer < k) l = mid + 1;
		else r = mid;
	//	itr++;
		//if(itr == 1) return;
	}
	//cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
	//cout << cnttt << " " << cnttt2 << "\n";
	//return;
	//cout << l << "\n";
	l--;
	for(int i = 1; i <= 524288; i++){
		for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
		for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
	}
	for(int i = 1; i <= n; i++){
		int pos = mp[a[i]];
		type = 0, val = l - a[i].fi - a[i].se, pluss = a[i].fi + a[i].se;
		gett(1, 1, n, 1, pos);
		type = 1, val = l - a[i].fi + a[i].se, pluss = a[i].fi - a[i].se;
		gett(1, 1, n, pos + 1, n);
		for(auto it : u1[i]) upd1(it.fi, it.se);
		for(auto it : u2[i]) upd2(it.fi, it.se);
		//continue;
		//point = a[i];
		//upd(1, 1, n, pos);
	}
	l++;
	//return;
	//cout << pq.size() << '\n';
	//assert(pq.size() <= k);
	while(pq.size() < k) pq.push(l);
	for(int i = 1; i <= k; i++){
		int x = pq.top();
		pq.pop();
		cout << x << "\n";
	}
	//cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	//freopen("road.inp", "r", stdin);
	//freopen("road.out", "w", stdout);
	//cin.tie(0);
	process();
}

Compilation message (stderr)

road_construction.cpp: In function 'void upd1(long long int, long long int)':
road_construction.cpp:55:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(; id2 < bit1[id].size(); id2 += id2 & -id2) bit1[id][id2]++;
      |        ~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'void upd2(long long int, long long int)':
road_construction.cpp:67:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(; id2 < bit2[id].size(); id2 += id2 & -id2) bit2[id][id2]++;
      |        ~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'long long int find_mn1(long long int, long long int)':
road_construction.cpp:142:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   if((answer + (1LL << i)) >= bit1[id].size()) continue;
      |      ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'long long int find_mn2(long long int, long long int)':
road_construction.cpp:154:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   if((answer + (1LL << i)) >= bit2[id].size()) continue;
      |      ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from road_construction.cpp:1:
road_construction.cpp: In function 'void gett(long long int, long long int, long long int, long long int, long long int)':
road_construction.cpp:190:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |     assert(posi < type2[id].size());
      |            ~~~~~^~~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'void process()':
road_construction.cpp:257:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  257 |   for(int j = 0; j < min_val1[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:262:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  262 |   for(int j = 0; j < min_val2[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:275:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  275 |    for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
      |                   ~~^~~~~~~~~~~~~~~~
road_construction.cpp:276:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  276 |    for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
      |                   ~~^~~~~~~~~~~~~~~~
road_construction.cpp:294:8: warning: unused variable 'pos' [-Wunused-variable]
  294 |    int pos = savee[i];
      |        ^~~
road_construction.cpp:358:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  358 |       if(it.se) for(int j = it.se; j < bit1[it.fi].size(); j += j & -j) bit1[it.fi][j] = 0;
      |                                    ~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:365:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  365 |       if(it.se) for(int j = it.se; j < bit2[it.fi].size(); j += j & -j) bit2[it.fi][j] = 0;
      |                                    ~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:399:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  399 |   for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
      |                  ~~^~~~~~~~~~~~~~~~
road_construction.cpp:400:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  400 |   for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
      |                  ~~^~~~~~~~~~~~~~~~
road_construction.cpp:418:18: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  418 |  while(pq.size() < k) pq.push(l);
      |        ~~~~~~~~~~^~~
road_construction.cpp:241:6: warning: unused variable 'itr' [-Wunused-variable]
  241 |  int itr = 0;
      |      ^~~

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