oj.uz

Submission #477914

# Submission time Handle Problem Language Result Execution time Memory
477914 2021-10-04T15:25:33 Z hohohaha Road Construction (JOI21_road_construction) C++14
100 / 100
 4196 ms 982404 KB 
// #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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 277928 KB Output is correct
2 Correct 934 ms 278212 KB Output is correct
3 Correct 365 ms 139288 KB Output is correct
4 Correct 354 ms 154564 KB Output is correct
5 Correct 625 ms 253296 KB Output is correct
6 Correct 7 ms 3788 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2677 ms 981592 KB Output is correct
2 Correct 2687 ms 981704 KB Output is correct
3 Correct 571 ms 268484 KB Output is correct
4 Correct 1934 ms 981480 KB Output is correct
5 Correct 2585 ms 981684 KB Output is correct
6 Correct 2636 ms 981636 KB Output is correct
7 Correct 2702 ms 981028 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1467 ms 517896 KB Output is correct
2 Correct 1486 ms 517772 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 913 ms 517764 KB Output is correct
5 Correct 1088 ms 517788 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1467 ms 517896 KB Output is correct
2 Correct 1486 ms 517772 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 913 ms 517764 KB Output is correct
5 Correct 1088 ms 517788 KB Output is correct
6 Correct 1436 ms 517688 KB Output is correct
7 Correct 1381 ms 517840 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1421 ms 517756 KB Output is correct
11 Correct 888 ms 517828 KB Output is correct
12 Correct 1092 ms 517724 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 277928 KB Output is correct
2 Correct 934 ms 278212 KB Output is correct
3 Correct 365 ms 139288 KB Output is correct
4 Correct 354 ms 154564 KB Output is correct
5 Correct 625 ms 253296 KB Output is correct
6 Correct 7 ms 3788 KB Output is correct
7 Correct 2973 ms 630532 KB Output is correct
8 Correct 2861 ms 630448 KB Output is correct
9 Correct 352 ms 154052 KB Output is correct
10 Correct 2293 ms 629736 KB Output is correct
11 Correct 2231 ms 629796 KB Output is correct
12 Correct 2172 ms 630488 KB Output is correct
13 Correct 2405 ms 628900 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 277928 KB Output is correct
2 Correct 934 ms 278212 KB Output is correct
3 Correct 365 ms 139288 KB Output is correct
4 Correct 354 ms 154564 KB Output is correct
5 Correct 625 ms 253296 KB Output is correct
6 Correct 7 ms 3788 KB Output is correct
7 Correct 2677 ms 981592 KB Output is correct
8 Correct 2687 ms 981704 KB Output is correct
9 Correct 571 ms 268484 KB Output is correct
10 Correct 1934 ms 981480 KB Output is correct
11 Correct 2585 ms 981684 KB Output is correct
12 Correct 2636 ms 981636 KB Output is correct
13 Correct 2702 ms 981028 KB Output is correct
14 Correct 1467 ms 517896 KB Output is correct
15 Correct 1486 ms 517772 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 913 ms 517764 KB Output is correct
18 Correct 1088 ms 517788 KB Output is correct
19 Correct 1436 ms 517688 KB Output is correct
20 Correct 1381 ms 517840 KB Output is correct
21 Correct 0 ms 332 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 1421 ms 517756 KB Output is correct
24 Correct 888 ms 517828 KB Output is correct
25 Correct 1092 ms 517724 KB Output is correct
26 Correct 2973 ms 630532 KB Output is correct
27 Correct 2861 ms 630448 KB Output is correct
28 Correct 352 ms 154052 KB Output is correct
29 Correct 2293 ms 629736 KB Output is correct
30 Correct 2231 ms 629796 KB Output is correct
31 Correct 2172 ms 630488 KB Output is correct
32 Correct 2405 ms 628900 KB Output is correct
33 Correct 4196 ms 982328 KB Output is correct
34 Correct 3913 ms 982384 KB Output is correct
35 Correct 3216 ms 981576 KB Output is correct
36 Correct 3077 ms 982068 KB Output is correct
37 Correct 2950 ms 982404 KB Output is correct
38 Correct 3145 ms 980884 KB Output is correct