oj.uz

답안 #423320

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
423320 2021-06-11T00:21:54 Z amoo_safar 모임들 (IOI18_meetings) C++17
60 / 100
 576 ms 115500 KB 
#include "meetings.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll Inf = 1e18;

const int N = 1e5 + 10;

int n, q;
vector<int> H, L, R;

ll ans[N];

struct node {
	int l, r;
	ll val_r;
	bool type; // false add, true set
	pll lz_set; // m h
	ll lz_add;
	node (){
		l = r = 0;
		type = false;
		lz_set = pll(0, 0);
		lz_add = 0;
	}
	void Apply_Add(ll x){
		if(type){
			lz_set.S += x;
			val_r = r * lz_set.F + lz_set.S;
		} else {
			lz_add += x;
			val_r += x;
		}
	}
	void Apply_Set(pll ln){
		type = true;
		lz_set = ln;
		val_r = r * lz_set.F + lz_set.S;
	}
};
node seg[N << 2];

void Shift(int id){
	if(seg[id].type){
		seg[id << 1].Apply_Set(seg[id].lz_set);
		seg[id << 1 | 1].Apply_Set(seg[id].lz_set);
		// seg[id].lz_set = pll(0, 0);
	} else {
		seg[id << 1].Apply_Add(seg[id].lz_add);
		seg[id << 1 | 1].Apply_Add(seg[id].lz_add);
	}
	seg[id].type = false;
	seg[id].lz_add = 0;
}
void Add(int id, int l, int r, ll x, int L, int R){
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		seg[id].Apply_Add(x);
		return ;
	}
	int mid = (L + R) >> 1;
	Shift(id);
	Add(id << 1, l, r, x, L, mid);
	Add(id<<1|1, l, r, x, mid, R);

	seg[id].val_r = seg[id << 1 | 1].val_r;
}
void Add(int id, int l, int r, pll ln, int L, int R){
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		seg[id].Apply_Set(ln);
		return ;
	}
	int mid = (L + R) >> 1;
	Shift(id);
	Add(id << 1, l, r, ln, L, mid);
	Add(id<<1|1, l, r, ln, mid, R);

	seg[id].val_r = seg[id << 1 | 1].val_r;
}
ll Get(int id, int idx, int L, int R){
	if(L + 1 == R) return seg[id].val_r;
	int mid = (L + R) >> 1;
	Shift(id);
	if(idx < mid)
		return Get(id << 1, idx, L, mid);
	return Get(id << 1 | 1, idx, mid, R);
}
void Build(int id, int L, int R){
	seg[id].r = R - 1;
	if(L + 1 == R) return ;
	int mid = (L + R) >> 1;
	Build(id << 1, L, mid);
	Build(id<<1|1, mid, R);
}

int BS(int id, int l, int r, pll ln, int L, int R){
	if(r <= L || R <= l) return R;
	
	int mid = (L + R) >> 1;
	
	if(l <= L && R <= r){
		if(seg[id].val_r > seg[id].r * ln.F + ln.S)
			return R;
		if(L + 1 == R)
			return L;
		
		Shift(id);
		int res = BS(id << 1, l, r, ln, L, mid);
		if(res < mid)
			return res;
		return BS(id << 1| 1, l, r, ln, mid, R);
	}
	Shift(id);
	int res = BS(id << 1, l, r, ln, L, mid);
	if(res < mid)
		return res;
	return BS(id<<1|1, l, r, ln, mid, R);
}


int par[N], sz[N];
int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
void Merge(int u, int v, ll md){
	u = Find(u);
	v = Find(v);
	// cerr << "^^ " << sz[u] << ' ' << sz[v] << '\n';
	assert(u < v);
	// phase 1 

	Add(1, v - sz[v] + 1, v + 1, 1ll * sz[u] * md, 0, n + 1);
	// cerr << "!! " << 1ll * sz[u] * md << '\n';
	// for(int i = v - sz[v] + 1; i <= v; i++){
		// cerr << "&& " << Get(1, i, 0, n + 1) << '+' << 1ll*sz[u]*md << '=';
		// Add(1, i, i + 1, 1ll * sz[u] * md, 0, n + 1);
		// cerr << Get(1, i, 0, n + 1) << '\n';
		// if(Get(1, i, 0, n + 1) == 3){
		// 	cerr << "pr : ";
		// 	for(int i = n; i >= 0; i--)
		// 		cerr << Get(1, i, 0, n + 1) << ' ';
		// 	cerr << '\n';
		// }
	// }
		// dp[i] += 1ll * sz[u] * md;
	// phase 2
	ll vl_u = Get(1, u, 0, n + 1);

	int lw = v - sz[v], hg = v + 1, mid;
	int bin_s = BS(1, lw + 1, hg, pll(md, vl_u - u * md), 0, n + 1);

	// while(lw + 1 < hg){
	// 	mid = (lw + hg) >> 1;
	// 	ll vl = Get(1, mid, 0, n + 1);
	// 	if(vl > vl_u + md * (mid - u))
	// 		lw = mid;
	// 	else 
	// 		hg = mid;
	// }
	if(bin_s == n + 1)
		bin_s = v + 1;
	// cerr << "! " << bin_s << ' ' << hg << '\n';
	// assert(bin_s == hg);
	Add(1, v - sz[v] + 1, bin_s, pll(md, vl_u - u * md), 0, n + 1);
	// for(int i = v - sz[v] + 1; i <= v; i++){
	// 	ll vl = Get(1, i, 0, n + 1);
	// 	if(vl > vl_u + md * (i - u))
	// 		Add(1, i, i + 1, pll(0, vl_u + md * (i - u)), 0, n + 1);
	// 		// dp[i] =dp[u] + md * (i - u);
	// 	else
	// 		break;
	// }
	sz[v] += sz[u];
	par[u] = v;
}

vector<int> Q[N];

pii A[N];
pii sg[N << 2];
void BB(int id, int L, int R){
	if(L + 1 == R){
		sg[id] = A[L];
		return ;
	}
	int mid = (L + R) >> 1;
	BB(id << 1, L, mid);
	BB(id<<1|1, mid, R);
	sg[id] = max(sg[id << 1], sg[id << 1 | 1]);
}
pii GT(int id, int l, int r, int L, int R){
	if(r <= L || R <= l) return pii(-1, -1);
	if(l <= L && R <= r) return sg[id];
	int mid = (L + R) >> 1;
	return max(GT(id << 1, l, r, L, mid), GT(id << 1|1, l, r, mid, R));
}


void Solve(int rv){
	vector<int> ord(n, 0);

	iota(all(ord), 0);
	sort(all(ord), [&](int i, int j){
		// if(H[i] == H[j])
		return pii(H[i], rv * i) < pii(H[j], rv * j); 
	});
	
	fill(sz, sz + N, 1);
	iota(par,par +N, 0);
	// fill(dp, dp + N, 0);
	Add(1, 0, n + 1, pll(0, 0), 0, n + 1);
	for(int i = 0; i < N; i++) Q[i].clear();
	for(int i = 0; i < n; i++) A[i] = pii(H[i], rv * i);
	BB(1, 0, n);
	////////////////////////////

	for(int i = 0; i < q; i++){
		pii mx = GT(1, L[i], R[i] + 1, 0, n);
		int idx = mx.S / rv;
		// int idx = L[i];
		// for(int j = L[i]; j <= R[i]; j++)
		// 	if(pii(H[j], rv * j) > pii(H[idx], rv * idx))
		// 		idx = j;
		// assert(idx == idx2);
		Q[idx].pb(i);
	}

	for(int i : ord){
		for(int q_id : Q[i]){
			ans[q_id] = min(ans[q_id], 1ll * H[i] * (i - L[q_id] + 1) + Get(1, R[q_id] + 1, 0, n + 1));
		}
		Merge(i, i + 1, H[i]);
		// cerr << "# " << i << '\n';
		// cerr << "!! ";
		// for(int i = 0; i <= n; i++)
		// 	cerr << Get(1, i, 0, n + 1) << ' ';
		// cerr << '\n';
	}
}

vector<long long> minimum_costs(vector<int> _H, vector<int> _L, vector<int> _R) {
	H = _H; L = _L; R = _R;
	n = H.size();
	q = L.size();

	Build(1, 0, n + 1);
	fill(ans, ans + N, Inf);

	Solve(+1);
	
	reverse(all(H));
	for(auto &x : L) x = n - 1 - x;
	for(auto &x : R) x = n - 1 - x;
	L.swap(R);

	Solve(-1);
	vector<ll> ANS;
	for(int i = 0; i < q; i++)
		ANS.pb(ans[i]);
	return ANS;
}

Compilation message

meetings.cpp: In function 'void Merge(int, int, ll)':
meetings.cpp:162:34: warning: unused variable 'mid' [-Wunused-variable]
  162 |  int lw = v - sz[v], hg = v + 1, mid;
      |                                  ^~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 22988 KB Output is correct
2 Correct 18 ms 23136 KB Output is correct
3 Correct 19 ms 23136 KB Output is correct
4 Correct 18 ms 23044 KB Output is correct
5 Correct 18 ms 23044 KB Output is correct
6 Correct 18 ms 23048 KB Output is correct
7 Correct 19 ms 23244 KB Output is correct
8 Correct 17 ms 23116 KB Output is correct
9 Correct 17 ms 23140 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 22988 KB Output is correct
2 Correct 18 ms 23136 KB Output is correct
3 Correct 19 ms 23136 KB Output is correct
4 Correct 18 ms 23044 KB Output is correct
5 Correct 18 ms 23044 KB Output is correct
6 Correct 18 ms 23048 KB Output is correct
7 Correct 19 ms 23244 KB Output is correct
8 Correct 17 ms 23116 KB Output is correct
9 Correct 17 ms 23140 KB Output is correct
10 Correct 32 ms 23492 KB Output is correct
11 Correct 31 ms 23548 KB Output is correct
12 Correct 31 ms 23528 KB Output is correct
13 Correct 30 ms 23564 KB Output is correct
14 Correct 30 ms 23604 KB Output is correct
15 Correct 29 ms 23556 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 22988 KB Output is correct
2 Correct 103 ms 25700 KB Output is correct
3 Correct 523 ms 33088 KB Output is correct
4 Correct 499 ms 34292 KB Output is correct
5 Correct 489 ms 36028 KB Output is correct
6 Correct 511 ms 36308 KB Output is correct
7 Correct 549 ms 36288 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 22988 KB Output is correct
2 Correct 103 ms 25700 KB Output is correct
3 Correct 523 ms 33088 KB Output is correct
4 Correct 499 ms 34292 KB Output is correct
5 Correct 489 ms 36028 KB Output is correct
6 Correct 511 ms 36308 KB Output is correct
7 Correct 549 ms 36288 KB Output is correct
8 Correct 575 ms 34372 KB Output is correct
9 Correct 510 ms 33812 KB Output is correct
10 Correct 540 ms 34412 KB Output is correct
11 Correct 568 ms 34252 KB Output is correct
12 Correct 512 ms 33828 KB Output is correct
13 Correct 536 ms 34384 KB Output is correct
14 Correct 576 ms 35516 KB Output is correct
15 Correct 506 ms 33816 KB Output is correct
16 Correct 551 ms 35440 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 22988 KB Output is correct
2 Correct 18 ms 23136 KB Output is correct
3 Correct 19 ms 23136 KB Output is correct
4 Correct 18 ms 23044 KB Output is correct
5 Correct 18 ms 23044 KB Output is correct
6 Correct 18 ms 23048 KB Output is correct
7 Correct 19 ms 23244 KB Output is correct
8 Correct 17 ms 23116 KB Output is correct
9 Correct 17 ms 23140 KB Output is correct
10 Correct 32 ms 23492 KB Output is correct
11 Correct 31 ms 23548 KB Output is correct
12 Correct 31 ms 23528 KB Output is correct
13 Correct 30 ms 23564 KB Output is correct
14 Correct 30 ms 23604 KB Output is correct
15 Correct 29 ms 23556 KB Output is correct
16 Correct 11 ms 22988 KB Output is correct
17 Correct 103 ms 25700 KB Output is correct
18 Correct 523 ms 33088 KB Output is correct
19 Correct 499 ms 34292 KB Output is correct
20 Correct 489 ms 36028 KB Output is correct
21 Correct 511 ms 36308 KB Output is correct
22 Correct 549 ms 36288 KB Output is correct
23 Correct 575 ms 34372 KB Output is correct
24 Correct 510 ms 33812 KB Output is correct
25 Correct 540 ms 34412 KB Output is correct
26 Correct 568 ms 34252 KB Output is correct
27 Correct 512 ms 33828 KB Output is correct
28 Correct 536 ms 34384 KB Output is correct
29 Correct 576 ms 35516 KB Output is correct
30 Correct 506 ms 33816 KB Output is correct
31 Correct 551 ms 35440 KB Output is correct
32 Runtime error 359 ms 115500 KB Execution killed with signal 11
33 Halted 0 ms 0 KB -