oj.uz

Submission #75193

# Submission time Handle Problem Language Result Execution time Memory
75193 2018-09-08T16:39:47 Z tmwilliamlin168 Meetings (IOI18_meetings) C++14
36 / 100
 1049 ms 234332 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=1e5;
int n, q, b[mxN], c[mxN+1], st[1<<18];
ll c1[5000][5000], c2[5000][5000];
vector<int> a;

void bld(int i=1, int l2=0, int r2=n-1) {
	if(l2==r2)
		st[i]=c[l2+1]-l2-1;
	else {
		int m2=(l2+r2)/2;
		bld(2*i, l2, m2);
		bld(2*i+1, m2+1, r2);
		st[i]=max(st[2*i], st[2*i+1]);
	}
}

ll qry(int l1, int r1, int i=1, int l2=0, int r2=n-1) {
	l1=max(l2, l1);
	r1=min(r2, r1);
	if(l1>r1)
		return 0;
	if(l1<=l2&&r2<=r1)
		return st[i];
	int m2=(l2+r2)/2;
	return max(qry(l1, r1, 2*i, l2, m2), qry(l1, r1, 2*i+1, m2+1, r2));
}

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
	n=h.size(), q=l.size();
	vector<ll> ans(q);
	if(n<=5000&&q<=5000) {
		for(int i=0; i<n; ++i) {
			int d=c1[i][i]=c2[i][i]=h[i];
			for(int j=i-1; j>=0; --j) {
				d=max(h[j], d);
				c1[i][j]=d+c1[i][j+1];
			}
			d=h[i];
			for(int j=i+1; j<n; ++j) {
				d=max(h[j], d);
				c2[i][j]=d+c2[i][j-1];
			}
		}
		for(int i=0; i<q; ++i) {
			ans[i]=LLONG_MAX;
			for(int j=l[i]; j<=r[i]; ++j)
				ans[i]=min(c1[j][l[i]]+c2[j][r[i]]-h[j], ans[i]);
		}
	} else {
		for(int i=0; i<n; ++i) {
			b[i]=i?b[i-1]:-1;
			if(h[i]>1) {
				a.push_back(i);
				b[i]=i;
			}
			if(h[i]>2)
				return ans;
		}
		c[n]=n;
		for(int i=n-1; i>=0; --i)
			c[i]=h[i]>1?i:c[i+1];
		bld();
		for(int i=0; i<q; ++i) {
			int l2=c[l[i]], r2=b[r[i]];
			ans[i]=l2>r[i]?r[i]-l[i]+1:max(l2-l[i], r[i]-r2);
			if(l2<r2)
				ans[i]=max(qry(l2, r2-1), ans[i]);
			ans[i]=2*(r[i]-l[i]+1)-ans[i];
		}
	}
	return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 90 ms 94904 KB Output is correct
3 Correct 92 ms 95008 KB Output is correct
4 Correct 92 ms 94948 KB Output is correct
5 Correct 92 ms 94972 KB Output is correct
6 Correct 91 ms 94940 KB Output is correct
7 Correct 92 ms 94952 KB Output is correct
8 Correct 91 ms 94904 KB Output is correct
9 Correct 91 ms 94980 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 90 ms 94904 KB Output is correct
3 Correct 92 ms 95008 KB Output is correct
4 Correct 92 ms 94948 KB Output is correct
5 Correct 92 ms 94972 KB Output is correct
6 Correct 91 ms 94940 KB Output is correct
7 Correct 92 ms 94952 KB Output is correct
8 Correct 91 ms 94904 KB Output is correct
9 Correct 91 ms 94980 KB Output is correct
10 Correct 522 ms 234300 KB Output is correct
11 Correct 1049 ms 234284 KB Output is correct
12 Correct 515 ms 234240 KB Output is correct
13 Correct 1048 ms 234280 KB Output is correct
14 Correct 520 ms 234232 KB Output is correct
15 Correct 528 ms 234332 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 40 ms 1788 KB Output is correct
3 Correct 122 ms 7476 KB Output is correct
4 Correct 109 ms 7188 KB Output is correct
5 Correct 63 ms 7444 KB Output is correct
6 Correct 94 ms 7536 KB Output is correct
7 Correct 97 ms 7536 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 40 ms 1788 KB Output is correct
3 Correct 122 ms 7476 KB Output is correct
4 Correct 109 ms 7188 KB Output is correct
5 Correct 63 ms 7444 KB Output is correct
6 Correct 94 ms 7536 KB Output is correct
7 Correct 97 ms 7536 KB Output is correct
8 Incorrect 57 ms 5400 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 90 ms 94904 KB Output is correct
3 Correct 92 ms 95008 KB Output is correct
4 Correct 92 ms 94948 KB Output is correct
5 Correct 92 ms 94972 KB Output is correct
6 Correct 91 ms 94940 KB Output is correct
7 Correct 92 ms 94952 KB Output is correct
8 Correct 91 ms 94904 KB Output is correct
9 Correct 91 ms 94980 KB Output is correct
10 Correct 522 ms 234300 KB Output is correct
11 Correct 1049 ms 234284 KB Output is correct
12 Correct 515 ms 234240 KB Output is correct
13 Correct 1048 ms 234280 KB Output is correct
14 Correct 520 ms 234232 KB Output is correct
15 Correct 528 ms 234332 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 40 ms 1788 KB Output is correct
18 Correct 122 ms 7476 KB Output is correct
19 Correct 109 ms 7188 KB Output is correct
20 Correct 63 ms 7444 KB Output is correct
21 Correct 94 ms 7536 KB Output is correct
22 Correct 97 ms 7536 KB Output is correct
23 Incorrect 57 ms 5400 KB Output isn't correct
24 Halted 0 ms 0 KB -