Submission #286683

#	Time	Username	Problem	Language	Result	Execution time	Memory
286683		AlanChen	Meetings (IOI18_meetings)	C++14	17 / 100	75 ms	19824 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>
using namespace std;

template<class A> using v=vector<A>;

typedef v<int> vi;
typedef long long ll;

#define sz(S) (int)(S).size()
#define pb push_back
#define rsz resize
#define f first
#define s second
#define mp make_pair

#define get4(a,b,c,d,...) d

#define lp3(x,a,b) for(int x=(a);x<(b);x++)
#define lp2(x,a) lp3(x,0,a)
#define lp1(a) lp2(loopvar,a)
#define lp(x...) get4(x,lp3,lp2,lp1,0)(x)


#define trv(x,S) for(auto& x:(S))

template<class A,class B> bool ckmax(A& a1,const B& b1) {return a1<b1?a1=b1,1:0;}
template<class A,class B> bool ckmin(A& a1,const B& b1) {return a1>b1?a1=b1,1:0;}













const int mx=101000;
int n;
int q;
v<ll> ans;

int rg[mx];
int lft1[mx];//[
int rt1[mx];//]

ll rmq[30][mx];

v<ll> minimum_costs(vi H, vi L,vi R)
{
	H.pb(2);
	n=sz(H),q=sz(L);
	ans.resize(q);

	int lst1=0;
	lp(i,n) if(H[i]==2)
	{
		lft1[i]=i,rt1[i]=i,rg[i]=0;
		lp(j,lst1,i) lft1[j]=lst1,rt1[j]=i-1,rg[j]=i-lst1;
		lst1=i+1;
	}
	lp(i,n) rmq[1][i]=rg[i];
	int x=2,lvl=2;
	while(x<=n)
	{
		lp(i,0,n-x+1) rmq[lvl][i]=max(rmq[lvl-1][i],rmq[lvl-1][i+x/2]);
		x*=2;
		lvl++;
	}

	lp(qn,q)
	{
		int l=L[qn];
		int r=R[qn];

		if(l==r) ans[qn]=H[l];
		else if(rt1[l]>=r)
		{
			ans[qn]=r-l+1;
		}
		else
		{
			int ls=0;
			int l1=l,r1=r;
			if(H[l]==1) ckmax(ls,rt1[l]-l+1),l1=rt1[l]+1;
			if(H[r]==1) ckmax(ls,r-lft1[r]+1),r1=lft1[r]-1;

			x=1,lvl=1;
			while(2*x<r1-l1+1) x*=2,lvl++;
			ckmax(ls,rmq[lvl][l1]);
			ckmax(ls,rmq[lvl][r1-x+1]);

			ans[qn]=2*(r-l+1)-ls;
		}
	}

	return ans;
}














/*
const int mx=1000000;
int q;
v<ll> ans;
ll pcost1[mx];
ll pcost2[mx];

void getcost(const v<ll>& H,int l,int r,ll rst[])
{

	v<pair<ll,int>> stps;

	ll ccost=0;
	lp(i,l,r+1)
	{
		stps.pb(mp(H[i],1)); ccost+=H[i];
		while(sz(stps)>1&&stps[sz(stps)-1].f>=stps[sz(stps)-2].f)
		{
			ccost+=(stps[sz(stps)-1].f-stps[sz(stps)-2].f)*stps[sz(stps)-2].s;
			stps[sz(stps)-2].f=stps[sz(stps)-1].f;
			stps[sz(stps)-2].s+=stps[sz(stps)-1].s;
			stps.pop_back();
		}
		rst[i]=ccost;
	}
}

v<ll> minimum_costs(vi H, vi L,vi R)
{
	q=sz(L);
	v<ll> hl(sz(H)),hlr(sz(H));
	vi Lr(q),Rr(q);
	lp(i,sz(H)) hl[i]=H[i];
	lp(i,sz(H)) hlr[i]=H[sz(H)-1-i];
	lp(i,q) Lr[i]=sz(H)-1-L[i];
	lp(i,q) Rr[i]=sz(H)-1-R[i];
	lp(i,q) swap(Lr[i],Rr[i]);


	ans.rsz(q);
	trv(x,ans) x=1ll<<60;

	lp(qn,q)
	{
		getcost(hl,L[qn],R[qn],pcost1);
		getcost(hlr,Lr[qn],Rr[qn],pcost2);
		lp(i,L[qn],R[qn]+1) ckmin(ans[qn],pcost1[i]+pcost2[sz(H)-1-i]-H[i]);

	}



	return ans;
}
 */

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