Submission #477911

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
477911	2021-10-04T15:20:18 Z	hohohaha	Road Construction (JOI21_road_construction)	C++14	100 / 100	7803 ms	1936588 KB

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, 3) {
		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	1648 ms	546936 KB	Output is correct
2	Correct	1705 ms	547316 KB	Output is correct
3	Correct	728 ms	269548 KB	Output is correct
4	Correct	743 ms	300484 KB	Output is correct
5	Correct	1182 ms	498936 KB	Output is correct
6	Correct	13 ms	7244 KB	Output is correct

Subtask #2

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5129 ms	1930752 KB	Output is correct
2	Correct	5108 ms	1930940 KB	Output is correct
3	Correct	1116 ms	528464 KB	Output is correct
4	Correct	3538 ms	1930732 KB	Output is correct
5	Correct	5046 ms	1930924 KB	Output is correct
6	Correct	5021 ms	1930804 KB	Output is correct
7	Correct	4941 ms	1930004 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2692 ms	1010040 KB	Output is correct
2	Correct	2569 ms	1009968 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	1772 ms	1009980 KB	Output is correct
5	Correct	2128 ms	1010016 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2692 ms	1010040 KB	Output is correct
2	Correct	2569 ms	1009968 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	1772 ms	1009980 KB	Output is correct
5	Correct	2128 ms	1010016 KB	Output is correct
6	Correct	2672 ms	1010124 KB	Output is correct
7	Correct	2614 ms	1010068 KB	Output is correct
8	Correct	0 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	2633 ms	1009984 KB	Output is correct
11	Correct	1676 ms	1010088 KB	Output is correct
12	Correct	2037 ms	1010216 KB	Output is correct

Subtask #5

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1648 ms	546936 KB	Output is correct
2	Correct	1705 ms	547316 KB	Output is correct
3	Correct	728 ms	269548 KB	Output is correct
4	Correct	743 ms	300484 KB	Output is correct
5	Correct	1182 ms	498936 KB	Output is correct
6	Correct	13 ms	7244 KB	Output is correct
7	Correct	5453 ms	1242472 KB	Output is correct
8	Correct	5597 ms	1242508 KB	Output is correct
9	Correct	717 ms	299344 KB	Output is correct
10	Correct	4219 ms	1241736 KB	Output is correct
11	Correct	3989 ms	1241600 KB	Output is correct
12	Correct	4010 ms	1242584 KB	Output is correct
13	Correct	4408 ms	1240908 KB	Output is correct

Subtask #6

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1648 ms	546936 KB	Output is correct
2	Correct	1705 ms	547316 KB	Output is correct
3	Correct	728 ms	269548 KB	Output is correct
4	Correct	743 ms	300484 KB	Output is correct
5	Correct	1182 ms	498936 KB	Output is correct
6	Correct	13 ms	7244 KB	Output is correct
7	Correct	5129 ms	1930752 KB	Output is correct
8	Correct	5108 ms	1930940 KB	Output is correct
9	Correct	1116 ms	528464 KB	Output is correct
10	Correct	3538 ms	1930732 KB	Output is correct
11	Correct	5046 ms	1930924 KB	Output is correct
12	Correct	5021 ms	1930804 KB	Output is correct
13	Correct	4941 ms	1930004 KB	Output is correct
14	Correct	2692 ms	1010040 KB	Output is correct
15	Correct	2569 ms	1009968 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	1772 ms	1009980 KB	Output is correct
18	Correct	2128 ms	1010016 KB	Output is correct
19	Correct	2672 ms	1010124 KB	Output is correct
20	Correct	2614 ms	1010068 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	0 ms	332 KB	Output is correct
23	Correct	2633 ms	1009984 KB	Output is correct
24	Correct	1676 ms	1010088 KB	Output is correct
25	Correct	2037 ms	1010216 KB	Output is correct
26	Correct	5453 ms	1242472 KB	Output is correct
27	Correct	5597 ms	1242508 KB	Output is correct
28	Correct	717 ms	299344 KB	Output is correct
29	Correct	4219 ms	1241736 KB	Output is correct
30	Correct	3989 ms	1241600 KB	Output is correct
31	Correct	4010 ms	1242584 KB	Output is correct
32	Correct	4408 ms	1240908 KB	Output is correct
33	Correct	7803 ms	1931484 KB	Output is correct
34	Correct	7610 ms	1936568 KB	Output is correct
35	Correct	6166 ms	1935784 KB	Output is correct
36	Correct	5691 ms	1936520 KB	Output is correct
37	Correct	5723 ms	1936588 KB	Output is correct
38	Correct	6312 ms	1935272 KB	Output is correct