oj.uz

답안 #477841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477841 2021-10-04T07:03:40 Z hohohaha Road Construction (JOI21_road_construction) C++17
33 / 100
 10000 ms 1950320 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)); 
}
int cv[maxn]; 
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; 
	fori(i, 1, n) cv[i] = mm[y[i]]; 
	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; 
		vv[i] = last; 
		ii mn = get(last, 1, n, cv[i], n); //cout << mn.fi << endl;
		ss.em(mn.fi - x[i] - y[i], ii(mn.se, i)); 
		last = sett(last, 1, n, cv[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 / 2) return; 
		ss.erase(t); 
		all.em(t.fi, ii(min(i, j), max(i, j)) ); 
		
		vv[i] = sett(vv[i], 1, n, cv[j], {inf, 0});
		ii mn = get(vv[i], 1, n, cv[j], n); 
		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) {
//		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 Execution timed out 10088 ms 52692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8600 ms 1940352 KB Output is correct
2 Correct 8296 ms 1940368 KB Output is correct
3 Correct 716 ms 268268 KB Output is correct
4 Correct 7289 ms 1950320 KB Output is correct
5 Correct 8613 ms 1935180 KB Output is correct
6 Correct 8339 ms 1935040 KB Output is correct
7 Correct 8603 ms 1939440 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6741 ms 1037048 KB Output is correct
2 Correct 6952 ms 1037080 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 4983 ms 1026540 KB Output is correct
5 Correct 4089 ms 1025540 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6741 ms 1037048 KB Output is correct
2 Correct 6952 ms 1037080 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 4983 ms 1026540 KB Output is correct
5 Correct 4089 ms 1025540 KB Output is correct
6 Correct 8028 ms 1037152 KB Output is correct
7 Correct 6681 ms 1037484 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 7143 ms 1036188 KB Output is correct
11 Correct 4525 ms 1026984 KB Output is correct
12 Correct 3961 ms 1025924 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10088 ms 52692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10088 ms 52692 KB Time limit exceeded
2 Halted 0 ms 0 KB -