oj.uz

Submission #765840

# Submission time Handle Problem Language Result Execution time Memory
765840 2023-06-25T06:17:58 Z ono_de206 Meetings (IOI18_meetings) C++14
19 / 100
 5500 ms 40264 KB 
#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int mxn = 8e5 + 10;
const long long inf = 1e18;
int h[mxn], LOG[mxn];
long long dp1[mxn], dp2[mxn];
pair<int, int> sp1[mxn][22], sp2[mxn][22];

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	int Q = L.size(), n = H.size();
	vector<long long> ret(Q);

	for(int i = 1; i <= n; i++) {
		h[i] = H[i - 1];
		sp1[i][0] = {h[i], i};
		sp2[i][0] = {h[i], -i};
	}
	for(int i = 1; i <= 20; i++) {
		for(int j = 1; j + (1 << i) - 1 <= n; j++) {
			sp1[j][i] = max(sp1[j][i - 1], sp1[j + (1 << (i - 1))][i - 1]);
			sp2[j][i] = max(sp2[j][i - 1], sp2[j + (1 << (i - 1))][i - 1]);
		}
	}
	stack<pair<int, int>> s;
	for(int i = 1; i <= n; i++) {
		while(s.size() && s.top().ff <= h[i]) s.pop();
		if(s.size() == 0) dp1[i] = i * h[i];
		else dp1[i] = dp1[s.top().ss] + 1LL * h[i] * (i - s.top().ss);
		s.push({h[i], i});
	}
	while(s.size()) s.pop();
	for(int i = n; i >= 1; i--) {
		while(s.size() && s.top().ff <= h[i]) s.pop();
		if(s.size() == 0) dp2[i] = (n - i + 1) * h[i];
		else dp2[i] = dp2[s.top().ss] + 1LL * h[i] * (s.top().ss - i);
		s.push({h[i], i});	
	}
	for(int i = 2; i <= n; i++) {
		LOG[i] = LOG[i / 2] + 1;
	}

	auto get1 = [&](int l, int r) -> pair<int, int> {
		int lg = LOG[r - l + 1];
		return max(sp1[l][lg], sp1[r - (1 << lg) + 1][lg]);
	};

	auto get2 = [&](int l, int r) -> pair<int, int> {
		int lg = LOG[r - l + 1];
		return max(sp2[l][lg], sp2[r - (1 << lg) + 1][lg]);
	};

	for(int i = 0; i < Q; i++) {
		int l = L[i] + 1, r = R[i] + 1;
		ret[i] = inf;
		for(int j = l; j <= r; j++) {
			auto mx1 = get1(l, j);
			auto mx2 = get2(j, r);
			mx2.ss *= -1;
			long long tmp = dp1[j] + dp2[j] - dp1[mx1.ss] - dp2[mx2.ss] + 1LL * (mx1.ss - l + 1) * mx1.ff + 1LL * (r - mx2.ss + 1) * mx2.ff - h[j];
			ret[i] = min(ret[i], tmp);
		}
	}
	return ret;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 2 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 2 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 75 ms 2328 KB Output is correct
11 Correct 207 ms 2336 KB Output is correct
12 Correct 72 ms 2384 KB Output is correct
13 Correct 219 ms 2332 KB Output is correct
14 Correct 77 ms 2336 KB Output is correct
15 Correct 71 ms 2380 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1231 ms 4508 KB Output is correct
3 Execution timed out 5529 ms 40264 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1231 ms 4508 KB Output is correct
3 Execution timed out 5529 ms 40264 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 2 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 75 ms 2328 KB Output is correct
11 Correct 207 ms 2336 KB Output is correct
12 Correct 72 ms 2384 KB Output is correct
13 Correct 219 ms 2332 KB Output is correct
14 Correct 77 ms 2336 KB Output is correct
15 Correct 71 ms 2380 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1231 ms 4508 KB Output is correct
18 Execution timed out 5529 ms 40264 KB Time limit exceeded
19 Halted 0 ms 0 KB -