Submission #139036

#	Time	Username	Problem	Language	Result	Execution time	Memory
139036		ckodser	Meetings (IOI18_meetings)	C++14	36 / 100	952 ms	5872 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<pii> vec;
ll rt[maxn];

ll seg[maxn*4];

void bild(ll l,ll r,ll node){
	if(l+1==r){
		seg[node]=rt[l];
		return;
	}
	ll mid=(l+r)/2;
	bild(l,mid,2*node);
	bild(mid,r,2*node+1);
	seg[node]=max(seg[2*node],seg[2*node+1]);
}
ll 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 0;
	ll mid=(L+R)/2;
	return max(findMx(L,mid,2*node,l,r),findMx(mid,R,2*node+1,l,r));
}
ll esht(pii a,pii b){
	pii c=mp(max(a.F,b.F),min(a.S,b.S));
	if(c.F<=c.S)return c.S-c.F+1;
	return 0;
}
ll findAns(ll l,ll r){
	ll x=lower_bound(vec.begin(),vec.end(),mp(l+1,(ll)0))-vec.begin()-1;
	ll ans=0;
	if(x>=0){
		ans=max(ans,esht(vec[x],mp(l,r)));
	}
	ll y=lower_bound(vec.begin(),vec.end(),mp(r+1,(ll)0))-vec.begin()-1;
	if(y>=0){
		ans=max(ans,esht(vec[y],mp(l,r)));
	}
	ans=max(ans,findMx(0,vec.size(),1,x+1,y));
	return ans;
}



vector<ll> solve(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<n;i++){
		if(h[i]==1){
			if(vec.empty()){
				vec.pb(mp(i,i));
			}else{
				if(vec.back().S==i-1){
					vec.back().S=i;
				}else{
					vec.pb(mp(i,i));
				}
			}
		}	
	}
	for(ll i=0;i<vec.size();i++){
		rt[i]=vec[i].S-vec[i].F+1;
	}
	bild(0,vec.size(),1);
	for(ll i=0;i<q;i++){
		anS[i]=2*(r[i]-l[i]+1)-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> solve(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:80:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<vec.size();i++){
             ~^~~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> easy(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:98:5: warning: unused variable 'n' [-Wunused-variable]
  ll n=h.size();
     ^

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