oj.uz

Submission #477908

# Submission time Handle Problem Language Result Execution time Memory
477908 2021-10-04T15:13:16 Z hohohaha Road Construction (JOI21_road_construction) C++14
65 / 100
 10000 ms 1958316 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]; 
vector<pair<int, ii> > all; 
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); 
	
	set<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 = *begin(ss); int i = t.se.se, j = t.se.fi; 
		ss.erase(t); 
		tmp.eb(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)); 
	}
	sort(all(tmp)); 
	fori(i, 1, tmp.size() - 1) { 
		assert(tmp[i] != tmp[i - 1]); 
	}
//	cout<< tmp.size() << endl;
	all.insert(end(all), all(tmp)); 
}

void solve() {
	cin >> n >> k; 
	fori(i, 1, n) { 
		cin >> x[i] >> y[i]; 
	}
	fori(tm, 0, 3) {
//		cout << tm << endl;
		fori(i,1, n) {
			swap(x[i], y[i]); 
			x[i] = -x[i]; 
		}
//		cout << x[1] << sp << y[1] << endl;
		handle(); 
	}
//	cout << all.size() << endl;
	sort(all(all)); 
	fori(i, 4, all.size() - 1) { 
		assert(all[i] != all[i - 4]); 
	}
	int ptr = 0; for(auto t: all) if(ptr + 1 < maxn and t != ans[ptr]) ans[++ptr] = t; 
	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 1870 ms 552840 KB Output is correct
2 Correct 1955 ms 553144 KB Output is correct
3 Correct 839 ms 272440 KB Output is correct
4 Correct 876 ms 303796 KB Output is correct
5 Correct 1457 ms 503784 KB Output is correct
6 Correct 17 ms 7376 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8504 ms 1958084 KB Output is correct
2 Correct 8579 ms 1958088 KB Output is correct
3 Correct 1299 ms 534328 KB Output is correct
4 Correct 5486 ms 1957788 KB Output is correct
5 Correct 8250 ms 1958052 KB Output is correct
6 Correct 7977 ms 1958316 KB Output is correct
7 Correct 7903 ms 1957308 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4458 ms 1031584 KB Output is correct
2 Correct 4514 ms 1031708 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 3462 ms 1031592 KB Output is correct
5 Correct 3676 ms 1031580 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4458 ms 1031584 KB Output is correct
2 Correct 4514 ms 1031708 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 3462 ms 1031592 KB Output is correct
5 Correct 3676 ms 1031580 KB Output is correct
6 Correct 4364 ms 1031492 KB Output is correct
7 Correct 4350 ms 1031500 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 4388 ms 1031620 KB Output is correct
11 Correct 3369 ms 1031532 KB Output is correct
12 Correct 3769 ms 1031620 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1870 ms 552840 KB Output is correct
2 Correct 1955 ms 553144 KB Output is correct
3 Correct 839 ms 272440 KB Output is correct
4 Correct 876 ms 303796 KB Output is correct
5 Correct 1457 ms 503784 KB Output is correct
6 Correct 17 ms 7376 KB Output is correct
7 Correct 7453 ms 1259076 KB Output is correct
8 Correct 7628 ms 1259108 KB Output is correct
9 Correct 858 ms 303608 KB Output is correct
10 Correct 5713 ms 1258252 KB Output is correct
11 Correct 5088 ms 1258324 KB Output is correct
12 Correct 5713 ms 1259008 KB Output is correct
13 Correct 6316 ms 1257760 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1870 ms 552840 KB Output is correct
2 Correct 1955 ms 553144 KB Output is correct
3 Correct 839 ms 272440 KB Output is correct
4 Correct 876 ms 303796 KB Output is correct
5 Correct 1457 ms 503784 KB Output is correct
6 Correct 17 ms 7376 KB Output is correct
7 Correct 8504 ms 1958084 KB Output is correct
8 Correct 8579 ms 1958088 KB Output is correct
9 Correct 1299 ms 534328 KB Output is correct
10 Correct 5486 ms 1957788 KB Output is correct
11 Correct 8250 ms 1958052 KB Output is correct
12 Correct 7977 ms 1958316 KB Output is correct
13 Correct 7903 ms 1957308 KB Output is correct
14 Correct 4458 ms 1031584 KB Output is correct
15 Correct 4514 ms 1031708 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 3462 ms 1031592 KB Output is correct
18 Correct 3676 ms 1031580 KB Output is correct
19 Correct 4364 ms 1031492 KB Output is correct
20 Correct 4350 ms 1031500 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 4388 ms 1031620 KB Output is correct
24 Correct 3369 ms 1031532 KB Output is correct
25 Correct 3769 ms 1031620 KB Output is correct
26 Correct 7453 ms 1259076 KB Output is correct
27 Correct 7628 ms 1259108 KB Output is correct
28 Correct 858 ms 303608 KB Output is correct
29 Correct 5713 ms 1258252 KB Output is correct
30 Correct 5088 ms 1258324 KB Output is correct
31 Correct 5713 ms 1259008 KB Output is correct
32 Correct 6316 ms 1257760 KB Output is correct
33 Execution timed out 10193 ms 1866804 KB Time limit exceeded
34 Halted 0 ms 0 KB -