oj.uz

답안 #477830

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477830 2021-10-04T05:26:07 Z hohohaha Road Construction (JOI21_road_construction) C++14
33 / 100
 10000 ms 1950968 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 2759 ms 552308 KB Output is correct
2 Correct 2787 ms 552048 KB Output is correct
3 Correct 1600 ms 525420 KB Output is correct
4 Execution timed out 10039 ms 527516 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9578 ms 1941572 KB Output is correct
2 Correct 9094 ms 1941432 KB Output is correct
3 Correct 1254 ms 525340 KB Output is correct
4 Correct 7282 ms 1950968 KB Output is correct
5 Correct 9327 ms 1935584 KB Output is correct
6 Correct 9019 ms 1935724 KB Output is correct
7 Correct 9193 ms 1940260 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7344 ms 1038972 KB Output is correct
2 Correct 7345 ms 1040160 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 3848 ms 1027492 KB Output is correct
5 Correct 3453 ms 1028852 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7344 ms 1038972 KB Output is correct
2 Correct 7345 ms 1040160 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 3848 ms 1027492 KB Output is correct
5 Correct 3453 ms 1028852 KB Output is correct
6 Correct 7411 ms 1040184 KB Output is correct
7 Correct 7374 ms 1040276 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 7108 ms 1038952 KB Output is correct
11 Correct 3705 ms 1027500 KB Output is correct
12 Correct 3528 ms 1028876 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2759 ms 552308 KB Output is correct
2 Correct 2787 ms 552048 KB Output is correct
3 Correct 1600 ms 525420 KB Output is correct
4 Execution timed out 10039 ms 527516 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2759 ms 552308 KB Output is correct
2 Correct 2787 ms 552048 KB Output is correct
3 Correct 1600 ms 525420 KB Output is correct
4 Execution timed out 10039 ms 527516 KB Time limit exceeded
5 Halted 0 ms 0 KB -