oj.uz

답안 #295275

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295275 2020-09-09T14:56:07 Z Kastanda 모임들 (IOI18_meetings) C++11
36 / 100
 1027 ms 301944 KB 
// M
#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long ll;
const int N = 100005, MXN = 5005, LG = 20;
int n, q, A[N], L[N], R[N], Nxt[N][LG], MX[N][LG];
int mx[MXN][MXN];
ll le[MXN][MXN], ri[MXN][MXN];
vector < ll > Brute()
{
	for (int len = 1; len <= n; len ++)
	{
		for (int l = 1, r = len; r <= n; l ++, r ++)
		{
			if (len == 1)
			{
				mx[l][r] = A[l];
				le[l][r] = ri[l][r] = A[l];
				continue;
			}
			mx[l][r] = max(mx[l][r - 1], A[r]);
			le[l][r] = le[l][r - 1] + mx[l][r];
			ri[l][r] = ri[l + 1][r] + mx[l][r];
		}
	}

	vector < ll > res;
	for (int i = 1; i <= q; i ++)
	{
		ll Mn = 1e18;
		for (int j = L[i]; j <= R[i]; j ++)
			Mn = min(Mn, le[j][R[i]] + ri[L[i]][j] - A[j]);
		res.push_back(Mn);
	}
	return res;
}

vector < long long > minimum_costs(vector < int > _H, vector < int > _L, vector < int > _R)
{
	n = (int)_H.size();
	q = (int)_L.size();
	for (int i = 1; i <= n; i ++)
		A[i] = _H[i - 1];
	for (int i = 1; i <= q; i ++)
		L[i] = _L[i - 1] + 1, R[i] = _R[i - 1] + 1;

	if (n <= 5000)
		return Brute();


	for (int i = 1; i <= n; i ++)
		assert(A[i] <= 2);

	int last = n + 1;
	for (int i = n; i; i --)
	{
		Nxt[i][0] = last;
		MX[i][0] = last - i - 1;
		if (A[i] == 2)
			last = i;
	}
	Nxt[n + 1][0] = n + 1;
	for (int j = 1; j < LG; j ++)
		for (int i = 1; i <= n + 1; i ++)
		{
			Nxt[i][j] = Nxt[Nxt[i][j - 1]][j - 1];
			MX[i][j] = max(MX[i][j - 1], MX[Nxt[i][j - 1]][j - 1]);
		}

	vector < int > vec;
	for (int i = 1; i <= n; i ++)
		if (A[i] == 2)
			vec.push_back(i);

	vector < ll > res;
	for (int i = 1; i <= q; i ++)
	{
		int lb = lower_bound(vec.begin(), vec.end(), L[i]) - vec.begin();
		int Mx = 0;

		if (lb == vec.size() || vec[lb] > R[i])
			Mx = R[i] - L[i] + 1;
		else
		{
			int nw = vec[lb];
			Mx = max(Mx, nw - L[i]);
			for (int j = LG - 1; j >= 0; j --)
				if (Nxt[nw][j] <= R[i])
					Mx = max(Mx, MX[nw][j]), nw = Nxt[nw][j];
			assert(Nxt[nw][0] > R[i]);
			Mx = max(Mx, R[i] - nw);
		}

		ll sm = (R[i] - L[i] + 1) * 2LL - Mx;
		res.push_back(sm);
	}
	return res;
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:82:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   if (lb == vec.size() || vec[lb] > R[i])
      |       ~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 251 ms 124776 KB Output is correct
3 Correct 259 ms 124792 KB Output is correct
4 Correct 255 ms 124920 KB Output is correct
5 Correct 253 ms 124792 KB Output is correct
6 Correct 255 ms 124884 KB Output is correct
7 Correct 251 ms 124792 KB Output is correct
8 Correct 254 ms 124924 KB Output is correct
9 Correct 259 ms 124792 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 251 ms 124776 KB Output is correct
3 Correct 259 ms 124792 KB Output is correct
4 Correct 255 ms 124920 KB Output is correct
5 Correct 253 ms 124792 KB Output is correct
6 Correct 255 ms 124884 KB Output is correct
7 Correct 251 ms 124792 KB Output is correct
8 Correct 254 ms 124924 KB Output is correct
9 Correct 259 ms 124792 KB Output is correct
10 Correct 822 ms 301816 KB Output is correct
11 Correct 1026 ms 301944 KB Output is correct
12 Correct 798 ms 301816 KB Output is correct
13 Correct 1027 ms 301944 KB Output is correct
14 Correct 807 ms 301816 KB Output is correct
15 Correct 817 ms 301772 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 38 ms 3464 KB Output is correct
3 Correct 200 ms 23024 KB Output is correct
4 Correct 116 ms 22640 KB Output is correct
5 Correct 131 ms 22896 KB Output is correct
6 Correct 138 ms 22900 KB Output is correct
7 Correct 140 ms 22816 KB Output is correct

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 38 ms 3464 KB Output is correct
3 Correct 200 ms 23024 KB Output is correct
4 Correct 116 ms 22640 KB Output is correct
5 Correct 131 ms 22896 KB Output is correct
6 Correct 138 ms 22900 KB Output is correct
7 Correct 140 ms 22816 KB Output is correct
8 Runtime error 84 ms 9592 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 251 ms 124776 KB Output is correct
3 Correct 259 ms 124792 KB Output is correct
4 Correct 255 ms 124920 KB Output is correct
5 Correct 253 ms 124792 KB Output is correct
6 Correct 255 ms 124884 KB Output is correct
7 Correct 251 ms 124792 KB Output is correct
8 Correct 254 ms 124924 KB Output is correct
9 Correct 259 ms 124792 KB Output is correct
10 Correct 822 ms 301816 KB Output is correct
11 Correct 1026 ms 301944 KB Output is correct
12 Correct 798 ms 301816 KB Output is correct
13 Correct 1027 ms 301944 KB Output is correct
14 Correct 807 ms 301816 KB Output is correct
15 Correct 817 ms 301772 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 38 ms 3464 KB Output is correct
18 Correct 200 ms 23024 KB Output is correct
19 Correct 116 ms 22640 KB Output is correct
20 Correct 131 ms 22896 KB Output is correct
21 Correct 138 ms 22900 KB Output is correct
22 Correct 140 ms 22816 KB Output is correct
23 Runtime error 84 ms 9592 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -