oj.uz

답안 #122511

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122511 2019-06-28T13:30:32 Z Sorting 모임들 (IOI18_meetings) C++14
36 / 100
 710 ms 196620 KB 
#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

const long long inf = 1e18;
const long long MAXN1 = 5007;
const long long MAXN = 75e4 + 7;

int n, q;
long long cost[MAXN1][MAXN1];

struct node{
	int m, l, r, cnt;

	node(){}
	node(int m, int l, int r){
		this->m = m;
		this->l = l;
		this->r = r;
		cnt = 1;
	}
};

node unite(node lvalue, node rvalue){
	node ret;

	ret.m = max(max(lvalue.m, rvalue.m), lvalue.r + rvalue.l);
	ret.l = (lvalue.l == lvalue.cnt) ? (lvalue.l + rvalue.l) : lvalue.l;
	ret.r = (rvalue.l == rvalue.cnt) ? (lvalue.r + rvalue.r) : rvalue.r;

	ret.m = max(ret.m, max(ret.l, ret.r));
	ret.cnt = lvalue.cnt + rvalue.cnt;

	return ret;
}

node st[4 * MAXN];
int a[MAXN];

void init(int idx, int l, int r){
	if(l == r){
		st[idx].m = st[idx].l = st[idx].r = (a[l] == 1);
		st[idx].cnt = 1;

		return;
	}

	int mid = (l + r) >> 1;

	init(2 * idx, l, mid);
	init(2 * idx + 1, mid + 1, r);

	st[idx] = unite(st[2 * idx], st[2 * idx + 1]);
}

node query(int idx, int l, int r, int sl, int sr){
	if(sl <= l && r <= sr){
		return st[idx];
	}
	if(l > sr || r < sl){
		return node(0, 0, 0);
	}

	int mid = (l + r) >> 1;

	node lvalue = query(2 * idx, l, mid, sl, sr);
	node rvalue = query(2 * idx + 1, mid + 1, r, sl, sr);

	return unite(lvalue, rvalue);
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
	vector<long long> ret;

	n = (int)H.size();
	q = (int)L.size();

	if(n > 5000 || q > 5000){
		for(int i = 0; i < n; i++){
			a[i] = H[i];
		}

		init(1, 0, n - 1);

		for(int i = 0; i < q; i++){
			ret.push_back(2 * (R[i] - L[i] + 1) - query(1, 0, n - 1, L[i], R[i]).m);
		}

		return ret;
	}

	for(int i = 0; i < n; i++){
		long long mx = H[i];
		cost[i][i] = H[i];

		for(int j = i + 1; j < n; j++){
			mx = max(mx, (long long)H[j]);
			cost[i][j] = cost[i][j - 1] + mx; 
		}

		mx = H[i];
		for(int j = i - 1; j >= 0; j--){
			mx = max(mx, (long long)H[j]);
			cost[i][j] = cost[i][j + 1] + mx;
		}
	}

	for(int i = 0; i < q; i++){
		int l = L[i], r = R[i];
		long long ans = inf;

		for(int j = l; j <= r; j++){
			ans = min(ans, cost[j][l] + cost[j][r] - H[j]);
		}

		ret.push_back(ans);
	}

	return ret;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 81 ms 82812 KB Output is correct
3 Correct 83 ms 82908 KB Output is correct
4 Correct 83 ms 82820 KB Output is correct
5 Correct 83 ms 82812 KB Output is correct
6 Correct 82 ms 82880 KB Output is correct
7 Correct 81 ms 82880 KB Output is correct
8 Correct 81 ms 82800 KB Output is correct
9 Correct 82 ms 82908 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 81 ms 82812 KB Output is correct
3 Correct 83 ms 82908 KB Output is correct
4 Correct 83 ms 82820 KB Output is correct
5 Correct 83 ms 82812 KB Output is correct
6 Correct 82 ms 82880 KB Output is correct
7 Correct 81 ms 82880 KB Output is correct
8 Correct 81 ms 82800 KB Output is correct
9 Correct 82 ms 82908 KB Output is correct
10 Correct 477 ms 196504 KB Output is correct
11 Correct 663 ms 196596 KB Output is correct
12 Correct 479 ms 196620 KB Output is correct
13 Correct 710 ms 196504 KB Output is correct
14 Correct 488 ms 196580 KB Output is correct
15 Correct 481 ms 196548 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 41 ms 2032 KB Output is correct
3 Correct 127 ms 8336 KB Output is correct
4 Correct 128 ms 8404 KB Output is correct
5 Correct 99 ms 8360 KB Output is correct
6 Correct 118 ms 8304 KB Output is correct
7 Correct 126 ms 8316 KB Output is correct

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 41 ms 2032 KB Output is correct
3 Correct 127 ms 8336 KB Output is correct
4 Correct 128 ms 8404 KB Output is correct
5 Correct 99 ms 8360 KB Output is correct
6 Correct 118 ms 8304 KB Output is correct
7 Correct 126 ms 8316 KB Output is correct
8 Incorrect 129 ms 8324 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 81 ms 82812 KB Output is correct
3 Correct 83 ms 82908 KB Output is correct
4 Correct 83 ms 82820 KB Output is correct
5 Correct 83 ms 82812 KB Output is correct
6 Correct 82 ms 82880 KB Output is correct
7 Correct 81 ms 82880 KB Output is correct
8 Correct 81 ms 82800 KB Output is correct
9 Correct 82 ms 82908 KB Output is correct
10 Correct 477 ms 196504 KB Output is correct
11 Correct 663 ms 196596 KB Output is correct
12 Correct 479 ms 196620 KB Output is correct
13 Correct 710 ms 196504 KB Output is correct
14 Correct 488 ms 196580 KB Output is correct
15 Correct 481 ms 196548 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 41 ms 2032 KB Output is correct
18 Correct 127 ms 8336 KB Output is correct
19 Correct 128 ms 8404 KB Output is correct
20 Correct 99 ms 8360 KB Output is correct
21 Correct 118 ms 8304 KB Output is correct
22 Correct 126 ms 8316 KB Output is correct
23 Incorrect 129 ms 8324 KB Output isn't correct
24 Halted 0 ms 0 KB -