oj.uz

Submission #295298

# Submission time Handle Problem Language Result Execution time Memory
295298 2020-09-09T15:13:56 Z Saboon Meetings (IOI18_meetings) C++17
36 / 100
 1028 ms 9720 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int maxn = 1e5 + 10;
ll dp[maxn];

struct node{
	int pre = 0;
	int suf = 0;
	int sum = 0;
	bool fil = 0;
} seg[4*maxn];

node merge(node a, node b){
	node ret;
	ret.pre = a.pre + (a.fil * b.pre);
	ret.suf = b.suf + (b.fil * a.suf);
	ret.fil = (a.fil & b.fil);
	ret.sum = max({a.sum, b.sum, a.suf+b.pre});
	return ret;
}

node get(int id, int L, int R, int l, int r){
	if (l <= L and R <= r)
		return seg[id];
	int mid = (L + R) >> 1;
	if (r <= mid)
		return get(2*id+0, L, mid, l, r);
	if (mid <= l)
		return get(2*id+1, mid, R, l, r);
	return merge(get(2*id+0, L, mid, l, r), get(2*id+1, mid, R, l, r));
}

void add(int id, int L, int R, int idx){
	if (idx < L or R <= idx)
		return;
	if (L+1 == R){
		seg[id].pre = seg[id].suf = seg[id].sum = seg[id].fil = 1;
		return;
	}
	int mid = (L + R) >> 1;
	add(2*id+0, L, mid, idx);
	add(2*id+1, mid, R, idx);
	seg[id] = merge(seg[2*id+0], seg[2*id+1]);
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	int n = H.size(), Q = L.size();
	if (n <= 5000 and Q <= 5000){
		vector<ll> C(Q);
		for (int j = 0; j < Q; j++){
			C[j] = inf;
			stack<pair<int,int>> S;
			ll Sum = 0;
			for (int i = L[j]; i <= R[j]; i++){
				int cnt = 1;
				while (!S.empty() and S.top().first <= H[i]){
					Sum -= 1LL*S.top().first*S.top().second;
					cnt += S.top().second;
					S.pop();
				}
				Sum += 1LL*H[i]*cnt;
				dp[i] = Sum;
				S.push({H[i],cnt});
			}
			while (!S.empty())
				S.pop();
			Sum = 0;
			for (int i = R[j]; i >= L[j]; i--){
				int cnt = 1;
				while (!S.empty() and S.top().first <= H[i]){
					Sum -= 1LL*S.top().first*S.top().second;
					cnt += S.top().second;
					S.pop();
				}
				Sum += 1LL*H[i]*cnt;
				C[j] = min(C[j], Sum+dp[i]-H[i]);
				S.push({H[i],cnt});
			}
		}
		return C;
	}
	if (*max_element(H.begin(),H.end()) <= 2){
		for (int i = 0; i < n; i++)
			if (H[i] == 1)
				add(1, 0, n, i);
		vector<ll> C(Q);
		for (int q = 0; q < Q; q++){
			int len = R[q]-L[q]+1;
			C[q] = 2*len - get(1, 0, n, L[q], R[q]+1).sum;
		}
		return C;
	}
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:96:1: warning: control reaches end of non-void function [-Wreturn-type]
   96 | }
      | ^

Subtask #1
4.0 / 4.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 341 ms 672 KB Output is correct
11 Correct 1028 ms 684 KB Output is correct
12 Correct 324 ms 760 KB Output is correct
13 Correct 992 ms 760 KB Output is correct
14 Correct 225 ms 760 KB Output is correct
15 Correct 250 ms 640 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 37 ms 2168 KB Output is correct
3 Correct 123 ms 9592 KB Output is correct
4 Correct 135 ms 9720 KB Output is correct
5 Correct 93 ms 9720 KB Output is correct
6 Correct 105 ms 7800 KB Output is correct
7 Correct 113 ms 7672 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 37 ms 2168 KB Output is correct
3 Correct 123 ms 9592 KB Output is correct
4 Correct 135 ms 9720 KB Output is correct
5 Correct 93 ms 9720 KB Output is correct
6 Correct 105 ms 7800 KB Output is correct
7 Correct 113 ms 7672 KB Output is correct
8 Incorrect 111 ms 9592 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 341 ms 672 KB Output is correct
11 Correct 1028 ms 684 KB Output is correct
12 Correct 324 ms 760 KB Output is correct
13 Correct 992 ms 760 KB Output is correct
14 Correct 225 ms 760 KB Output is correct
15 Correct 250 ms 640 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 37 ms 2168 KB Output is correct
18 Correct 123 ms 9592 KB Output is correct
19 Correct 135 ms 9720 KB Output is correct
20 Correct 93 ms 9720 KB Output is correct
21 Correct 105 ms 7800 KB Output is correct
22 Correct 113 ms 7672 KB Output is correct
23 Incorrect 111 ms 9592 KB Output isn't correct
24 Halted 0 ms 0 KB -