oj.uz

답안 #477853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477853 2021-10-04T07:36:26 Z hohohaha Road Construction (JOI21_road_construction) C++14
33 / 100
 10000 ms 1949020 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("input.inp","r",stdin);
// freopen("output.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 = 1e13; 
int n, k; 
int x[maxn], y[maxn]; 
set<pair<int, ii> > all; 
 
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) mn = min(mn, l->mn); 
		if(r) 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; 
	return min(get(now->l, l, m, ll, rr), get(now->r, m + 1, r, ll, rr)); 
}
void handle() { 
	vector<pair<ii, int> > pp; 
	
	fori(i, 1, n) pp.eb(ii(x[i], y[i]), i); 
	map<int, int> mm; for(auto t: pp) mm[t.fi.se] = 1; int tt = 0; for(auto &t: mm) t.se = ++tt; 
	
	vector<node*> vv(n + 1, 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; 
//		cout << x[i] << sp << y[i] << endl;
		vv[i] = last; 
		ii mn = get(last, 1, n, mm[y[i]], n); //cout << mn.fi << endl;
		ss.em(mn.fi - x[i] - y[i], ii(mn.se, i)); 
		last = sett(last, 1, n, mm[y[i]], ii(x[i] + y[i], i)); 
	}
	fori(tm, 1, k) { 
		auto t = *begin(ss); int i = t.se.se, j = t.se.fi; 
//		cout << t.fi << endl;
		if(t.fi >= inf) return; 
		ss.erase(t); 
		all.em(t.fi, ii(min(i, j), max(i, j)) ); 
		
		vv[i] = sett(vv[i], 1, n, mm[y[j]], {inf, 0});
		ii mn = get(vv[i], 1, n, mm[y[i]], n); 
		ss.em(mn.fi - x[i] - y[i], ii(mn.se, i)); 
//		cout << "ss: " << ss.size() << endl;
//		for(auto t: ss) cout << t.fi << sp; cout << endl;
	}
}
 
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]; 
		}
		handle(); 
	}
	fori(i, 1, k) { 
		cout << begin(all)->fi << endl;
		all.erase(begin(all)); 
	}
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2730 ms 552252 KB Output is correct
2 Correct 2739 ms 552032 KB Output is correct
3 Correct 1614 ms 525512 KB Output is correct
4 Execution timed out 10117 ms 527640 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9006 ms 1938584 KB Output is correct
2 Correct 8853 ms 1938968 KB Output is correct
3 Correct 1243 ms 525356 KB Output is correct
4 Correct 7170 ms 1949020 KB Output is correct
5 Correct 9572 ms 1933684 KB Output is correct
6 Correct 9798 ms 1933784 KB Output is correct
7 Correct 9617 ms 1938128 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7918 ms 1035180 KB Output is correct
2 Correct 8003 ms 1035776 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4025 ms 1027416 KB Output is correct
5 Correct 3808 ms 1028812 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7918 ms 1035180 KB Output is correct
2 Correct 8003 ms 1035776 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4025 ms 1027416 KB Output is correct
5 Correct 3808 ms 1028812 KB Output is correct
6 Correct 7934 ms 1040288 KB Output is correct
7 Correct 8063 ms 1040380 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 7818 ms 1038868 KB Output is correct
11 Correct 4073 ms 1027528 KB Output is correct
12 Correct 3731 ms 1028900 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2730 ms 552252 KB Output is correct
2 Correct 2739 ms 552032 KB Output is correct
3 Correct 1614 ms 525512 KB Output is correct
4 Execution timed out 10117 ms 527640 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2730 ms 552252 KB Output is correct
2 Correct 2739 ms 552032 KB Output is correct
3 Correct 1614 ms 525512 KB Output is correct
4 Execution timed out 10117 ms 527640 KB Time limit exceeded
5 Halted 0 ms 0 KB -