Submission #477914

#	Time	Username	Problem	Language	Result	Execution time	Memory
477914		hohohaha	Road Construction (JOI21_road_construction)	C++14	100 / 100	4196 ms	982404 KiB

road_construction

// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
 
using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
 
#define li long long
#define ld long double
#define ii pair<int, int>
#define dd pair<double, double>
#define lii pair<li, li>
#define ldd pair<ld, ld>
#define vi vector<int> // typedef vector<int> vi + #define int long long -> vi is still vector of 32 bit int, which took me 2 hours to figure out
#define vd vector<double>
// untested
#define vli vector<li>
#define vld vector<ld>
#define vii vector<ii>
#define vdd vector<dd>
#define vlii vector<lii>
#define vldd vector<ldd>
#define vvi vector<vi>
#define vvii vector<vii>
#define vvli vector<vli>
#define vvlii vector<vlii>
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front
 
#define fr front
#define bc back
 
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)
 
#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '
 
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long // for convenience, not recommended
// #define double long double
 
void solve();
 
signed main() {
// freopen("test.inp","r",stdin);
// freopen("test.out","w",stdout);
   fastio();
   int tc = 1;
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}
 
#define int long long
const ld pi = 4 * atan(1.0), eps = 1e-9;
const int maxn = 2.5e5 + 5, inf = 1e16; 
int n, k; 
int x[maxn], y[maxn]; 
pair<int, ii> all[4 * maxn]; int ptrr;  
pair<int, ii> ans[maxn]; 
struct node { 
	ii mn = { inf, 0}; 
	node * l = 0, * r = 0; 
	node(ii mn) : mn(mn), l(0), r(0) {}; 
	node(node * l, node * r): l(l), r(r) { 
		if(l != nullptr) mn = min(mn, l->mn); 
		if(r != nullptr) mn = min(mn, r->mn); 
	}
}; 
node * build(int l, int r) { 
	if(l == r) return new node(ii(inf, inf)); 
	int m = l + r >> 1; return new node(build(l, m), build(m + 1, r)); 
}
node* sett(node * now, int l, int r, int p, ii v) { 
	if(l == r) return new node(v);
	int m = l + r >> 1; return p <= m? new node(sett(now->l, l, m, p, v), now->r): new node(now->l, sett(now->r, m + 1, r, p, v)); 
}
ii get(node *now, int l, int r, int ll, int rr) { 
	if(l > rr or ll > r) return {inf, 0}; 
	if(ll <= l and r <= rr) return now->mn; 
	int m = l + r >> 1; 
	ii re = {inf, 0}; if(now->l) re = min(re, get(now->l, l, m, ll, rr)); if(now->r) re = min(re, get(now->r, m + 1, r, ll, rr)); 
	return re; 
}
void handle() { 
	vector<pair<ii, int> > pp, byy; 
	
	fori(i, 1, n) pp.eb(ii(x[i], y[i]), i), byy.eb(ii(y[i], x[i]), i); 
	sort(all(byy)); vi conv(n + 5, 0); int cnt = 0; for(auto t: byy) conv[t.se] = ++cnt; 
	vector<node*> vv(n + 5, 0); 
	
	priority_queue<pair<int, ii>, vector<pair<int, ii> > , greater< pair<int, ii> > > ss; 
	sort(all(pp)); reverse(all(pp));
	node* last = build(1, n);  
	
	for(auto t: pp) { 
		int i = t.se; 
		vv[i] = last; 
		ii mn = get(last, 1, n, conv[i], n); //cout << mn.fi << endl;
		if(mn.fi < inf) ss.em(mn.fi - x[i] - y[i], ii(mn.se, i)); 
		last = sett(last, 1, n, conv[i], ii(x[i] + y[i], i)); 
	}
	vector<pair<int, ii> > tmp; 
	fori(tm, 1, k) { 
		if(ss.empty() ) break; 
		auto t = ss.top(); int i = t.se.se, j = t.se.fi; 
		ss.pop();  
		all[++ptrr] = mp(t.fi, ii(min(i, j), max(i, j)) ); 
		
		vv[i] = sett(vv[i], 1, n, conv[j], {inf, 0});
		ii mn = get(vv[i], 1, n, conv[i], n); 
		if(mn.fi < inf) ss.em(mn.fi - x[i] - y[i], ii(mn.se, i)); 
	}
}

void solve() {
	cin >> n >> k; 
	fori(i, 1, n) { 
		cin >> x[i] >> y[i]; 
	}
	fori(tm, 0, 1) {
		fori(i,1, n) {
			swap(x[i], y[i]); 
			x[i] = -x[i]; 
		}
		handle(); 
	}
	sort(all + 1, all + ptrr + 1); 
	int ptr = 0; fori(i, 1, ptrr) if(ptr + 1 < maxn and all[i] != ans[ptr]) ans[++ptr] = all[i]; 
	fori(i, 1, k) cout << ans[i].fi << endl;
}

Compilation message (stderr)

road_construction.cpp: In function 'node* build(long long int, long long int)':
road_construction.cpp:95:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |  int m = l + r >> 1; return new node(build(l, m), build(m + 1, r));
      |          ~~^~~
road_construction.cpp: In function 'node* sett(node*, long long int, long long int, long long int, std::pair<long long int, long long int>)':
road_construction.cpp:99:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |  int m = l + r >> 1; return p <= m? new node(sett(now->l, l, m, p, v), now->r): new node(now->l, sett(now->r, m + 1, r, p, v));
      |          ~~^~~
road_construction.cpp: In function 'std::pair<long long int, long long int> get(node*, long long int, long long int, long long int, long long int)':
road_construction.cpp:104:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |  int m = l + r >> 1;
      |          ~~^~~

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