Submission #139019

#	Time	Username	Problem	Language	Result	Execution time	Memory
139019		ckodser	Meetings (IOI18_meetings)	C++14	19 / 100	950 ms	1144 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;


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);
	}
	exit(1);
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> easy(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:23: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