oj.uz

답안 #817635

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817635 2023-08-09T14:19:53 Z NothingXD 모임들 (IOI18_meetings) C++17
100 / 100
 2921 ms 457456 KB 
#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e6 + 10;

struct Seg{
	ll l, r, lazy2;
	pll lazy1;
};
Seg seg[maxn << 2];

void merge(int v)
{
	seg[v].l = seg[v << 1].l;
	seg[v].r = seg[v << 1 | 1].r;
}

//void shift(int v, int l, int r);

void update1(int v, int l, int r, ll a, ll b){
	seg[v].l = a + b * l;
	seg[v].r = a + b * (r-1);
	seg[v].lazy1 = {a, b};
}

void update2(int v, int l, int r, ll val){
	seg[v].l += val;
	seg[v].r += val;
	seg[v].lazy1.F += val;
	seg[v].lazy2 += val;
}


void shift(int v, int l, int r){
	if (seg[v].lazy2 == 0 && seg[v].lazy1.S == -1) return;
	int mid = (l + r) >> 1;
	if (seg[v].lazy2 != 0){
		update2(v << 1, l, mid, seg[v].lazy2);
		update2(v << 1 | 1, mid, r, seg[v].lazy2);
	}
	if (seg[v].lazy1.S != -1){
		update1(v << 1, l, mid, seg[v].lazy1.F, seg[v].lazy1.S);
		update1(v << 1 | 1, mid, r, seg[v].lazy1.F, seg[v].lazy1.S);
	}
	seg[v].lazy1 = {0, -1};
	seg[v].lazy2 = 0;
}

void change(int v, int l, int r, int ql, int qr, ll a, ll b){
//	if (v == 1) debug(ql, qr, a, b);
	if (qr <= l || r <= ql) return;
	if (!(ql <= l && r <= qr)){
		shift(v, l, r);
		int mid = (l + r) >> 1;
		change(v << 1, l, mid, ql, qr, a, b);
		change(v << 1 | 1, mid, r, ql, qr, a, b);
	}
	else{
	//	debug(v, l, r, ql, qr, a, b, seg[v].l, seg[v].r);
		if (a + b * l <= seg[v].l && a + b * (r-1) <= seg[v].r){
	//		debug(seg[v].l, seg[v].r, seg[v].mx, seg[v].lazy1.F, seg[v].lazy1.S);
			update1(v, l, r, a, b);
			return;
		}
		if (a + b * l >= seg[v].l && a + b * (r-1) >= seg[v].r) return;
		shift(v, l, r);
		int mid = (l + r) >> 1;
		change(v << 1, l, mid, ql, qr, a, b);
		change(v << 1 | 1, mid, r, ql, qr, a, b);
	}
	merge(v);
	//seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

void add(int v, int l, int r, int ql, int qr, ll val){
	//if (v == 1) debug(ql, qr, val);
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
//		debug(v, l, r, ql, qr, val);
		update2(v, l, r, val);
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	add(v << 1, l, mid, ql, qr, val);
	add(v << 1 | 1, mid, r, ql, qr, val);
	merge(v);
	//seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

ll get(int v, int l, int r, int idx){
	//if (v == 1) debug(idx);
	if (l + 1 == r) return seg[v].l;
	shift(v, l, r);
	int mid = (l + r) >> 1;
	if (idx < mid) return get(v << 1, l, mid, idx);
	else return get(v << 1 | 1, mid, r, idx);
}


const int lg = 20;
const ll inf = 1e18;

int n, q, h[maxn], queryl[maxn], queryr[maxn];
ll ans[maxn];
pii rmq[lg][maxn];
vector<pair<pii,int>> Q[maxn];

pii getmx(int l, int r){
	r++;
	int x = 31 - __builtin_clz(r-l);
	return max(rmq[x][l], rmq[x][r-(1<<x)]);
}

void carttree(int l, int r){
	if (r < l) return;
	int mid = getmx(l, r).S;
	mid = abs(mid);
	carttree(l, mid-1);
	carttree(mid+1, r);
	//		debug(x, y);
	for (auto [tmp, idx]: Q[mid]){
		ans[idx] = min(ans[idx], get(1, 0, n, tmp.S) + 1ll * (mid-tmp.F+1) * h[mid]);
	}
	add(1, 0, n, mid, r+1, 1ll * (mid-l+1) * h[mid]);
	if (l == mid) return;
	ll tmp = get(1, 0, n, mid-1);
	tmp -= 1ll * (mid-1) * h[mid];
	change(1, 0, n, mid, r+1, tmp, h[mid]);
}

void solve(bool flg){
	vector<pii> val;
	for (int i = 0; i < n; i++){
		Q[i].clear();
	}
	for (int i = 1; i < 4*maxn; i++){
		seg[i].l = 0;
		seg[i].r = 0;
		seg[i].lazy1 = {0, -1};
		seg[i].lazy2 = 0;
	}
	for (int i = 0; i < n; i++){
		if (!flg){
			rmq[0][i] = {h[i], i};
		}
		else{
			rmq[0][i] = {h[i], -i};
		}
	}
	for (int i = 1; i < lg; i++){
		for (int j = 0; j + (1 << i) <= n; j++){
			rmq[i][j] = max(rmq[i-1][j], rmq[i-1][j+(1<<(i-1))]);
		}
	}
	for (int i = 0; i < q; i++){
		int mx = abs(getmx(queryl[i], queryr[i]).S);
		Q[mx].push_back({{queryl[i], queryr[i]}, i});
	}
	carttree(0, n-1);
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	n = H.size();
	q = L.size();
	for (int i = 0; i < n; i++){
		h[i] = H[i];
	}
	for (int i = 0; i < q; i++){
		queryl[i] = L[i];
		queryr[i] = R[i];
		ans[i] = inf;
	}
	solve(false);
	//	debug("----------------");
	//	for (int i = 0; i < q; i++) debug(i, ans[i]);
	for (int i = 0; i < q; i++){
		queryl[i] = n-R[i]-1;
		queryr[i] = n-L[i]-1;
	}
	for (int i = 0; i < n/2; i++){
		swap(h[i], h[n-i-1]);
	}
	solve(true);
	vector<ll> res;
	for (int i = 0; i < q; i++) res.push_back(ans[i]);
	return res;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 180296 KB Output is correct
2 Correct 90 ms 180764 KB Output is correct
3 Correct 96 ms 180648 KB Output is correct
4 Correct 89 ms 180764 KB Output is correct
5 Correct 89 ms 180660 KB Output is correct
6 Correct 104 ms 180812 KB Output is correct
7 Correct 91 ms 180676 KB Output is correct
8 Correct 106 ms 180872 KB Output is correct
9 Correct 89 ms 180800 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 180296 KB Output is correct
2 Correct 90 ms 180764 KB Output is correct
3 Correct 96 ms 180648 KB Output is correct
4 Correct 89 ms 180764 KB Output is correct
5 Correct 89 ms 180660 KB Output is correct
6 Correct 104 ms 180812 KB Output is correct
7 Correct 91 ms 180676 KB Output is correct
8 Correct 106 ms 180872 KB Output is correct
9 Correct 89 ms 180800 KB Output is correct
10 Correct 103 ms 181468 KB Output is correct
11 Correct 98 ms 181448 KB Output is correct
12 Correct 108 ms 181452 KB Output is correct
13 Correct 108 ms 181456 KB Output is correct
14 Correct 98 ms 181832 KB Output is correct
15 Correct 95 ms 181448 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 180332 KB Output is correct
2 Correct 147 ms 185568 KB Output is correct
3 Correct 288 ms 207608 KB Output is correct
4 Correct 251 ms 201992 KB Output is correct
5 Correct 241 ms 207172 KB Output is correct
6 Correct 310 ms 208472 KB Output is correct
7 Correct 325 ms 210448 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 180332 KB Output is correct
2 Correct 147 ms 185568 KB Output is correct
3 Correct 288 ms 207608 KB Output is correct
4 Correct 251 ms 201992 KB Output is correct
5 Correct 241 ms 207172 KB Output is correct
6 Correct 310 ms 208472 KB Output is correct
7 Correct 325 ms 210448 KB Output is correct
8 Correct 316 ms 202696 KB Output is correct
9 Correct 225 ms 202260 KB Output is correct
10 Correct 249 ms 202752 KB Output is correct
11 Correct 247 ms 201976 KB Output is correct
12 Correct 224 ms 201492 KB Output is correct
13 Correct 244 ms 202572 KB Output is correct
14 Correct 287 ms 208096 KB Output is correct
15 Correct 253 ms 202024 KB Output is correct
16 Correct 307 ms 207852 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 180296 KB Output is correct
2 Correct 90 ms 180764 KB Output is correct
3 Correct 96 ms 180648 KB Output is correct
4 Correct 89 ms 180764 KB Output is correct
5 Correct 89 ms 180660 KB Output is correct
6 Correct 104 ms 180812 KB Output is correct
7 Correct 91 ms 180676 KB Output is correct
8 Correct 106 ms 180872 KB Output is correct
9 Correct 89 ms 180800 KB Output is correct
10 Correct 103 ms 181468 KB Output is correct
11 Correct 98 ms 181448 KB Output is correct
12 Correct 108 ms 181452 KB Output is correct
13 Correct 108 ms 181456 KB Output is correct
14 Correct 98 ms 181832 KB Output is correct
15 Correct 95 ms 181448 KB Output is correct
16 Correct 105 ms 180332 KB Output is correct
17 Correct 147 ms 185568 KB Output is correct
18 Correct 288 ms 207608 KB Output is correct
19 Correct 251 ms 201992 KB Output is correct
20 Correct 241 ms 207172 KB Output is correct
21 Correct 310 ms 208472 KB Output is correct
22 Correct 325 ms 210448 KB Output is correct
23 Correct 316 ms 202696 KB Output is correct
24 Correct 225 ms 202260 KB Output is correct
25 Correct 249 ms 202752 KB Output is correct
26 Correct 247 ms 201976 KB Output is correct
27 Correct 224 ms 201492 KB Output is correct
28 Correct 244 ms 202572 KB Output is correct
29 Correct 287 ms 208096 KB Output is correct
30 Correct 253 ms 202024 KB Output is correct
31 Correct 307 ms 207852 KB Output is correct
32 Correct 1749 ms 355204 KB Output is correct
33 Correct 1382 ms 375616 KB Output is correct
34 Correct 1538 ms 378172 KB Output is correct
35 Correct 1919 ms 374480 KB Output is correct
36 Correct 1246 ms 374936 KB Output is correct
37 Correct 1503 ms 378524 KB Output is correct
38 Correct 2921 ms 420680 KB Output is correct
39 Correct 2575 ms 420824 KB Output is correct
40 Correct 1888 ms 382904 KB Output is correct
41 Correct 2308 ms 457456 KB Output is correct
42 Correct 2242 ms 454732 KB Output is correct
43 Correct 2301 ms 454724 KB Output is correct
44 Correct 2340 ms 420444 KB Output is correct