Submission #75193

#	Time	Username	Problem	Language	Result	Execution time	Memory
75193		tmwilliamlin168	Meetings (IOI18_meetings)	C++14	36 / 100	1049 ms	234332 KiB

meetings

#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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40