oj.uz

답안 #160124

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160124 2019-10-26T04:35:10 Z qkxwsm 모임들 (IOI18_meetings) C++14
60 / 100
 1237 ms 393720 KB 
#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 131313
#define LLINF 2696969696969696969

typedef long long ll;
typedef double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, Q;
ll arr[MAXN];
pii query[MAXN];
int dp[22][MAXN];
int lt[22][MAXN], rt[22][MAXN];
int sparse[22][20][MAXN];
ll mx[5013][5013], pmx[5013][5013];
vl ans;

int qmax(int w, int l, int r)
{
	if (l > r) return 0;
	int sz = 31 - __builtin_clz(r - l + 1);
	return max(sparse[w][sz][l], sparse[w][sz][r - (1 << sz) + 1]);
}
int solve(int v, int i, int j, bool flag)
{
	if (i > j) return 0;
	if (v == 0) return 0;
	if (qmax(21, i, j) < v)
	{
		return (j - i + 1) + solve(v - 1, i, j, flag);
	}
	int res = 0;
	if (flag)
	{
		int pos = lt[v][j];
		res = qmax(v - 1, i, pos - 1);
		ckmax(res, solve(v - 1, pos + 1, j, flag));
		//answer on the right side.
	}
	else
	{
		int pos = rt[v][i];
		res = qmax(v - 1, pos + 1, j);
		ckmax(res, solve(v - 1, i, pos - 1, flag));
	}
	//solve (i...j) with value v.
	//you actually wanna figure out how much dough you save
	res += (j - i + 1);
	return res;
}

vl minimum_costs(vi h, vi l, vi r)
{
	N = SZ(h); Q = SZ(r); ans.resize(Q);
	FOR(i, 0, N)
	{
		arr[i] = h[i];
		sparse[21][0][i] = arr[i];
	}
	FOR(j, 1, 20)
	{
		FOR(k, 0, N - (1 << j) + 1)
		{
			sparse[21][j][k] = max(sparse[21][j - 1][k], sparse[21][j - 1][k + (1 << (j - 1))]);
		}
	}
	FOR(i, 0, Q)
	{
		query[i] = {l[i], r[i]};
	}
	if (N <= 5013 && Q <= 5013)
	{
		FOR(i, 0, N)
		{
			mx[i][i] = arr[i];
			FOR(j, i + 1, N)
			{
				mx[i][j] = max(mx[i][j - 1], arr[j]);
				mx[j][i] = mx[i][j];
			}
		}
		FOR(i, 0, N)
		{
			FOR(j, 0, N)
			{
				pmx[i][j + 1] = pmx[i][j] + mx[i][j];
			}
		}
		FOR(i, 0, Q)
		{
			int l = query[i].fi, r = query[i].se;
			ans[i] = LLINF;
			FOR(j, l, r + 1)
			{
				ckmin(ans[i], pmx[j][r + 1] - pmx[j][l]);
			}
		}
		return ans;
	}
	FOR(i, 1, 21)
	{
		vi guys;
		guys.PB(-1);
		FOR(j, 0, N)
		{
			if (arr[j] > i) guys.PB(j);
		}
		guys.PB(N);
		FOR(j, 1, SZ(guys))
		{
			int best = 0;
			FOR(k, guys[j - 1] + 1, guys[j])
			{
				ckmax(best, dp[i - 1][k]);
			}
			best += (guys[j] - guys[j - 1] - 1);
			FOR(k, guys[j - 1] + 1, guys[j])
			{
				ckmax(dp[i][k], best);
			}
		}
		//build the sparse table!
		FOR(j, 0, N)
		{
			sparse[i][0][j] = dp[i][j];
		}
		FOR(j, 1, 20)
		{
			FOR(k, 0, N - (1 << j) + 1)
			{
				sparse[i][j][k] = max(sparse[i][j - 1][k], sparse[i][j - 1][k + (1 << (j - 1))]);
			}
		}
	}
	FOR(i, 0, N)
	{
		FOR(j, 0, 22)
		{
			lt[j][i] = (i == 0 ? -1 : lt[j][i - 1]);
			if (arr[i] >= j) lt[j][i] = i;
		}
	}
	FORD(i, N, 0)
	{
		FOR(j, 0, 22)
		{
			rt[j][i] = (i == N - 1 ? N : rt[j][i + 1]);
			if (arr[i] >= j) rt[j][i] = i;
		}
	}
	//first occurence of >= x before y.
	FOR(i, 0, Q)
	{
		int l = query[i].fi, r = query[i].se;
		int mx = qmax(21, l, r), lf = rt[mx][l], rg = lt[mx][r];
		ans[i] = qmax(mx - 1, lf + 1, rg - 1);
		ckmax(ans[i], solve(mx - 1, l, lf - 1, 0));
		ckmax(ans[i], solve(mx - 1, rg + 1, r, 1));
		//idk solve!
		ans[i] = mx * (r - l + 1) - ans[i];
	}
	//you just store how much you can save;
	return ans;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 268 ms 165752 KB Output is correct
3 Correct 278 ms 165624 KB Output is correct
4 Correct 278 ms 165624 KB Output is correct
5 Correct 274 ms 165624 KB Output is correct
6 Correct 272 ms 165616 KB Output is correct
7 Correct 277 ms 165700 KB Output is correct
8 Correct 269 ms 165624 KB Output is correct
9 Correct 270 ms 165596 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 268 ms 165752 KB Output is correct
3 Correct 278 ms 165624 KB Output is correct
4 Correct 278 ms 165624 KB Output is correct
5 Correct 274 ms 165624 KB Output is correct
6 Correct 272 ms 165616 KB Output is correct
7 Correct 277 ms 165700 KB Output is correct
8 Correct 269 ms 165624 KB Output is correct
9 Correct 270 ms 165596 KB Output is correct
10 Correct 1046 ms 393460 KB Output is correct
11 Correct 1233 ms 393540 KB Output is correct
12 Correct 1028 ms 393648 KB Output is correct
13 Correct 1237 ms 393468 KB Output is correct
14 Correct 1044 ms 393720 KB Output is correct
15 Correct 1037 ms 393592 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 41 ms 14200 KB Output is correct
3 Correct 244 ms 161840 KB Output is correct
4 Correct 251 ms 161784 KB Output is correct
5 Correct 227 ms 161840 KB Output is correct
6 Correct 230 ms 161816 KB Output is correct
7 Correct 233 ms 161712 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 41 ms 14200 KB Output is correct
3 Correct 244 ms 161840 KB Output is correct
4 Correct 251 ms 161784 KB Output is correct
5 Correct 227 ms 161840 KB Output is correct
6 Correct 230 ms 161816 KB Output is correct
7 Correct 233 ms 161712 KB Output is correct
8 Correct 380 ms 162408 KB Output is correct
9 Correct 267 ms 162228 KB Output is correct
10 Correct 375 ms 162364 KB Output is correct
11 Correct 377 ms 162376 KB Output is correct
12 Correct 269 ms 162272 KB Output is correct
13 Correct 387 ms 162400 KB Output is correct
14 Correct 265 ms 162180 KB Output is correct
15 Correct 515 ms 162056 KB Output is correct
16 Correct 269 ms 158544 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 268 ms 165752 KB Output is correct
3 Correct 278 ms 165624 KB Output is correct
4 Correct 278 ms 165624 KB Output is correct
5 Correct 274 ms 165624 KB Output is correct
6 Correct 272 ms 165616 KB Output is correct
7 Correct 277 ms 165700 KB Output is correct
8 Correct 269 ms 165624 KB Output is correct
9 Correct 270 ms 165596 KB Output is correct
10 Correct 1046 ms 393460 KB Output is correct
11 Correct 1233 ms 393540 KB Output is correct
12 Correct 1028 ms 393648 KB Output is correct
13 Correct 1237 ms 393468 KB Output is correct
14 Correct 1044 ms 393720 KB Output is correct
15 Correct 1037 ms 393592 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 41 ms 14200 KB Output is correct
18 Correct 244 ms 161840 KB Output is correct
19 Correct 251 ms 161784 KB Output is correct
20 Correct 227 ms 161840 KB Output is correct
21 Correct 230 ms 161816 KB Output is correct
22 Correct 233 ms 161712 KB Output is correct
23 Correct 380 ms 162408 KB Output is correct
24 Correct 267 ms 162228 KB Output is correct
25 Correct 375 ms 162364 KB Output is correct
26 Correct 377 ms 162376 KB Output is correct
27 Correct 269 ms 162272 KB Output is correct
28 Correct 387 ms 162400 KB Output is correct
29 Correct 265 ms 162180 KB Output is correct
30 Correct 515 ms 162056 KB Output is correct
31 Correct 269 ms 158544 KB Output is correct
32 Runtime error 431 ms 44268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Halted 0 ms 0 KB -