oj.uz

답안 #477854

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477854 2021-10-04T07:37:16 Z hohohaha Road Construction (JOI21_road_construction) C++14
33 / 100
 10000 ms 1948140 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 2810 ms 552256 KB Output is correct
2 Correct 2968 ms 552028 KB Output is correct
3 Correct 1735 ms 525356 KB Output is correct
4 Execution timed out 10061 ms 527476 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9099 ms 1938488 KB Output is correct
2 Correct 9304 ms 1938456 KB Output is correct
3 Correct 1305 ms 525328 KB Output is correct
4 Correct 7713 ms 1948140 KB Output is correct
5 Correct 9850 ms 1932684 KB Output is correct
6 Correct 9574 ms 1932648 KB Output is correct
7 Correct 9763 ms 1937080 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7591 ms 1035208 KB Output is correct
2 Correct 7531 ms 1035104 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3830 ms 1024616 KB Output is correct
5 Correct 3568 ms 1023700 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7591 ms 1035208 KB Output is correct
2 Correct 7531 ms 1035104 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3830 ms 1024616 KB Output is correct
5 Correct 3568 ms 1023700 KB Output is correct
6 Correct 7589 ms 1035128 KB Output is correct
7 Correct 7381 ms 1035292 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 7184 ms 1033844 KB Output is correct
11 Correct 3804 ms 1024636 KB Output is correct
12 Correct 3358 ms 1023580 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2810 ms 552256 KB Output is correct
2 Correct 2968 ms 552028 KB Output is correct
3 Correct 1735 ms 525356 KB Output is correct
4 Execution timed out 10061 ms 527476 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2810 ms 552256 KB Output is correct
2 Correct 2968 ms 552028 KB Output is correct
3 Correct 1735 ms 525356 KB Output is correct
4 Execution timed out 10061 ms 527476 KB Time limit exceeded
5 Halted 0 ms 0 KB -