Submission #571495

#	Time	Username	Problem	Language	Result	Execution time	Memory
571495		dennisstar	Meetings (IOI18_meetings)	C++17	0 / 100	61 ms	25224 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	int n=H.size();
	vector<ll> ans(L.size(), 1e18);

	for (int tr=0; tr<2; tr++) {
		vector<vector<int>> qu(n);

		vector<pair<int, int>> st(1<<21);
		for (int i=0; i<n; i++) st[i+(1<<20)]={H[i], -i};
		for (int i=(1<<20)-1; i; i--) st[i]=max(st[i*2], st[i*2+1]);

		auto getmx = [&](int l, int r) {
			l+=(1<<20);
			r+=(1<<20);
			pair<int, int> rt(0, 0);
			while (l<=r) {
				if (l%2) rt=max(rt, st[l]), l++;
				if (r%2==0) rt=max(rt, st[r]), r--;
				l/=2;
				r/=2;
			}
			return -rt.second;
		};

		for (int i=0; i<L.size(); i++) qu[getmx(L[i], R[i])].emplace_back(i);

		vector<array<int, 2>> ct(n, {-1, -1});
		vector<int> pr(n), lc(n, -1), rc(n, -1);
		int rt=0;
		for (int i=1, lst; i<n; i++) {
			lst=i-1;
			while (H[lst]<H[i]&&lst!=rt) lst=pr[lst];
			if (H[lst]<H[i]) pr[rt]=i, lc[i]=rt, rt=i;
			else if (rc[lst]==-1) rc[lst]=i, pr[i]=lst;
			else pr[rc[lst]]=i, lc[i]=rc[lst], rc[lst]=i, pr[i]=lst;
		}
		for (int i=0; i<n; i++) ct[i]={lc[i], rc[i]};

		vector<ll> pl(n);
		vector<deque<tuple<ll, ll, int, int>>> sc(n);

		auto getv = [&](tuple<ll, ll, int, int> t, int x) {
			auto [a, b, l, r]=t;
			return a*x+b;
		};

		auto cal = [&](int u) {
			int l=get<2>(sc[u][0]), r=get<3>(sc[u].back());

			auto calc = [&](int rb) -> pair<ll, int> {
				if (rb<l) return {0, 0};
				int s=0, e=sc[u].size()-1;
				while (s<e) {
					int m=(s+e+1)/2;
					if (get<2>(sc[u][m])>rb) e=m-1;
					else s=m;
				}
				return {getv(sc[u][s], rb)+pl[u], s};
			};

			for (int i:qu[u]) {
				auto [v, j]=calc(R[i]);
				ans[i]=min(ans[i], v-(get<2>(sc[u][j])<u?H[u]*(L[i]-l):calc(L[i]-1).first));
			}
		};

		function<void(int)> dfs = [&](int u) {
			if (u==-1) return ;
			auto [l, r]=ct[u];
			dfs(l);
			dfs(r);
			if (l!=-1) swap(sc[l], sc[u]), pl[u]=pl[l];
			tuple<ll, ll, int, int> ins(H[u], (sc[u].size()?getv(sc[u].back(), u-1):0)+H[u]-1ll*u*H[u], u, u);
			if (r==-1) {
				sc[u].emplace_back(ins);
				cal(u);
				return ;
			}
			pl[r]+=1ll*(u-(sc[u].size()?get<2>(sc[u][0]):u)+1)*H[u];
			while (sc[r].size()) {
				if (getv(sc[r][0], get<3>(sc[r][0]))+pl[r]>=getv(ins, get<3>(sc[r][0]))+pl[u]) get<3>(ins)=get<3>(sc[r][0]), sc[r].pop_front();
				else if (getv(sc[r][0], get<2>(sc[r][0]))+pl[r]<getv(ins, get<3>(sc[r][0]))+pl[u]) break;
				else {
					int s=get<2>(sc[r][0]), e=get<3>(sc[r][1]);
					while (s<e) {
						int m=(s+e+1)/2;
						if (getv(sc[r][0], m)+pl[r]>=getv(ins, m)+pl[u]) s=m;
						else e=m-1;
					}
					get<2>(sc[r][0])=s+1;
					get<3>(ins)=s;
					break;
				}
			}
			sc[u].emplace_back(ins);
			if (sc[u].size()>=sc[r].size()) for (auto &i:sc[r]) get<1>(i)+=pl[r]-pl[u], sc[u].emplace_back(i);
			else {
				reverse(sc[u].begin(), sc[u].end());
				for (auto &i:sc[u]) get<1>(i)+=pl[u]-pl[r], sc[r].emplace_front(i);
				swap(sc[u], sc[r]);
				pl[u]=pl[r];
			}
			cal(u);
		};
		dfs(rt);

		reverse(H.begin(), H.end());
		for (int i=0; i<L.size(); i++) tie(L[i], R[i])=make_pair(n-1-R[i], n-1-L[i]);
	}

	return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for (int i=0; i<L.size(); i++) qu[getmx(L[i], R[i])].emplace_back(i);
      |                 ~^~~~~~~~~
meetings.cpp: In lambda function:
meetings.cpp:54:28: warning: unused variable 'r' [-Wunused-variable]
   54 |    int l=get<2>(sc[u][0]), r=get<3>(sc[u].back());
      |                            ^
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:114:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for (int i=0; i<L.size(); i++) tie(L[i], R[i])=make_pair(n-1-R[i], n-1-L[i]);
      |                 ~^~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40