Submission #571647

#	Time	Username	Problem	Language	Result	Execution time	Memory
571647		dennisstar	Meetings (IOI18_meetings)	C++17	100 / 100	2610 ms	755884 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
vector<deque<tuple<ll, ll, int, int>>> sc;
vector<int> H, L, R;
vector<ll> ans, pl;
vector<vector<int>> qu;
vector<array<int, 2>> ct;

pair<int, int> st[1<<21];

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

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

void cal(int u, int l) {
	for (int i:qu[u]) ans[i]=min(ans[i], calc(R[i], u)-1ll*H[u]*(L[i]-l));
}

void dfs(int u) { 
	if (u==-1) return ;
	auto [l, r]=ct[u];
	dfs(l);
	dfs(r);
	int lb=u;
	if (l!=-1) swap(sc[l], sc[u]), pl[u]=pl[l], lb=get<2>(sc[u][0]);
	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);
		for (int i:qu[u]) ans[i]=min(ans[i], 1ll*(R[i]-L[i]+1)*H[u]);
		return ;
	}
	pl[r]+=1ll*(u-lb+1)*H[u];
	swap(sc[r], sc[u]);
	swap(pl[r], pl[u]);
	cal(u, lb);
	swap(sc[r], sc[u]);
	swap(pl[r], pl[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<2>(sc[r][0]))+pl[u]) break;
		else {
			int s=get<2>(sc[r][0]), e=get<3>(sc[r][0]);
			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];
	}
}
 
vector<ll> minimum_costs(vector<int> hh, vector<int> ll, vector<int> rr) {
	int n=hh.size();
	H=hh;
	L=ll;
	R=rr;
	ans.resize(L.size(), 1e18);
	ct.resize(n, {-1, -1});
	qu.resize(n);
	pl.resize(n);
	sc.resize(n);

	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]};

	for (int tr=0; tr<2; tr++) {
		for (int i=0; i<n; i++) qu[i].clear(), pl[i]=0, sc[i].clear();

		memset(st, 0, sizeof(st));
		for (int i=0; i<n; i++) st[i+(1<<20)]={H[i], i*(tr?1:-1)};
		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*(tr?1:-1);
		};

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

		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]);
		rt=n-1-rt;
		for (auto &[l, r]:ct) tie(l, r)=make_pair(r==-1?-1:n-1-r, l==-1?-1:n-1-l);
		reverse(ct.begin(), ct.end());
	}
 
	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:105:27: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<int, int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
  105 |   memset(st, 0, sizeof(st));
      |                           ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from meetings.h:3,
                 from meetings.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~
meetings.cpp:122:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for (int i=0; i<L.size(); i++) qu[getmx(L[i], R[i])].emplace_back(i);
      |                 ~^~~~~~~~~
meetings.cpp:127:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   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: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40