Submission #139135

#	Time	Username	Problem	Language	Result	Execution time	Memory
139135		ckodser	Meetings (IOI18_meetings)	C++14	19 / 100	959 ms	9816 KiB

meetings

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

#define ll long long
#define pb push_back
#define ld long double
#define F first
#define S second
#define mp make_pair
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=1e5+500;
const ll inf=1e18+900;
const ll mod=1e9+7;


vector<ll> vec[maxn];
ll rt[maxn];
ll chand[maxn];
pair<ll,pii> seg[maxn*4];
map<pii,ll> ml;
ll n;

pair<ll,pii> merge(pair<ll,pii> a,pair<ll,pii> b){
	if(a.F<b.F){
		return b;
	}
	if(a.F>b.F){
		return a;
	}
	return mp(a.F,mp(a.S.F,b.S.S));
}
void bild(ll l,ll r,ll node){
	if(l+1==r){
		seg[node]=mp(rt[l],mp(chand[l],chand[l]));
		return;
	}
	ll mid=(l+r)/2;
	bild(l,mid,2*node);
	bild(mid,r,2*node+1);
	seg[node]=merge(seg[2*node],seg[2*node+1]);
}
pair<ll,pii> findMx(ll L,ll R,ll node,ll l,ll r){
	if(l<=L && R<=r){
		return seg[node];
	}
	if(r<=L || R<=l)return mp(-1,mp(0,0));
	ll mid=(L+R)/2;
	return merge(findMx(L,mid,2*node,l,r),findMx(mid,R,2*node+1,l,r));
}

ll findAns(ll l,ll r){
	if(l==r)return rt[l];
	if(ml.count(mp(l,r)))return ml[mp(l,r)];
	pair<ll,pii> er=findMx(0,n,1,l,r+1);
	ll mx=er.F;
	ll a=er.S.F;
	ll b=er.S.S;
	ll aa=vec[mx][a];
	ll bb=vec[mx][b];
	ll ans=inf;
	ans=min(ans,findAns(l,aa-1)+mx*(r-aa+1));
	ans=min(ans,findAns(bb+1,r)+mx*(bb-l+1));
	ans=min(ans,findAns(aa,bb)+mx*(r-l+1 - (bb-aa+1)));
	ml[mp(l,r)]=ans;
	return ans;
}



ll la[30];
vector<ll> solve(vector<int> h,vector<int> l,vector<int> r){
	vector<ll> anS(l.size());
	n=h.size();
	ll q=l.size();
	for(ll i=0;i<n;i++){
		rt[i]=h[i];
		chand[i]=la[h[i]];
		l[h[i]]++;
		vec[h[i]].pb(i);
	}
	bild(0,n,1);
	for(ll i=0;i<q;i++){
		anS[i]=findAns(l[i],r[i]);
	}
	return anS;
}






ll tmp[maxn];
vector<ll> easy(vector<int> h,vector<int> l,vector<int> r){
	vector<ll> anS(l.size());
	ll n=h.size();
	ll q=l.size();
	for(ll i=0;i<q;i++){
		stack<ll> stk;
		stk.push(l[i]);
		ll res=h[l[i]];
		tmp[l[i]]=res;
		for(ll j=l[i]+1;j<=r[i];j++){
			res+=h[j];
			while(stk.size() && h[stk.top()]<=h[j]){
				ll v=stk.top();
				stk.pop();
				ll f;
				if(stk.empty()){
					f=l[i];
				}else{
					f=stk.top()+1;
				}
				res+=(h[j]-h[v])*(v-f+1);
			}
			stk.push(j);
			tmp[j]=res;
		}
		while(stk.size())stk.pop();
		stk.push(r[i]);
		res=h[r[i]];
		tmp[r[i]]+=res;
		for(ll j=r[i]-1;j>=l[i];j--){
			res+=h[j];
			while(stk.size() && h[stk.top()]<=h[j]){
				ll v=stk.top();
				stk.pop();
				ll f;
				if(stk.empty()){
					f=r[i];
				}else{
					f=stk.top()-1;
				}
				res+=(h[j]-h[v])*(f-v+1);
			}
			stk.push(j);
			tmp[j]+=res;
		}
		while(stk.size())stk.pop();



		ll ans=inf;
		for(ll j=l[i];j<=r[i];j++){
			ans=min(ans,tmp[j]-h[j]);
			tmp[j]=0;
		}
		anS[i]=ans;
	}
	return anS;
}
vector<long long> minimum_costs(vector<int> H,vector<int> L,vector<int> R){
	if(H.size()<=5000 && L.size()<=5000){
		return easy(H,L,R);
	}
	ll mx=0;
	for(auto y:H){
		mx=max(mx,(ll)y);
	}
	if(mx>2 || H.size()>maxn || L.size()>maxn){
		exit(1);
	}
	return solve(H,L,R);
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> easy(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:99:5: warning: unused variable 'n' [-Wunused-variable]
  ll n=h.size();
     ^

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