Submission #1105496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105496		alexander707070	Meetings (IOI18_meetings)	C++14	19 / 100	369 ms	199876 KiB

meetings

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

const long long inf=1e17;

struct query{
	int l,r;
}qs[MAXN];

int n,q,h[MAXN];
vector< pair<long long,long long> > st;
vector<long long> ans;

long long res[5007][5007];

vector<long long> minimum_costs(vector<int> H,vector<int> L,vector<int> R){
	n=int(H.size());
	q=int(L.size());

	for(int i=1;i<=n;i++)h[i]=H[i-1];
	for(int i=1;i<=q;i++)qs[i]={L[i-1]+1,R[i-1]+1};

	h[0]=h[n+1]=inf;

	st.push_back({0,0});
	for(long long i=1;i<=n;i++){
		while(!st.empty() and h[i]>=h[st.back().first]){
			st.pop_back();
		}
		
		st.push_back({i,st.back().second+(i-st.back().first)*h[i]});

		for(int f=1;f<=q;f++){
			if(qs[f].l>i or qs[f].r<i)continue;

			int l=-1,r=st.size(),tt;

			while(l+1<r){
				tt=(l+r)/2;
				if(st[tt].first>=qs[f].l){
					r=tt;
				}else{
					l=tt;
				}
			}

			res[f][i]+=(st.back().second-st[r-1].second) - (qs[f].l-st[r-1].first-1)*h[st[r].first];
		}
	}

	st.clear();
	st.push_back({n+1,0});

	for(long long i=n;i>=1;i--){
		while(!st.empty() and h[i]>=h[st.back().first]){
			st.pop_back();
		}
		
		st.push_back({i,st.back().second+(st.back().first-i)*h[i]});

		for(int f=1;f<=q;f++){
			if(qs[f].l>i or qs[f].r<i)continue;

			int l=-1,r=st.size(),tt;

			while(l+1<r){
				tt=(l+r)/2;
				if(st[tt].first<=qs[f].r){
					r=tt;
				}else{
					l=tt;
				}
			}

			res[f][i]+=(st.back().second-st[r-1].second) - (st[r-1].first-qs[f].r-1)*h[st[r].first];
		}
	}

	ans.resize(q);
	for(int i=1;i<=q;i++){
		ans[i-1]=inf;

		for(int f=1;f<=n;f++){
			if(qs[i].l>f or qs[i].r<f)continue;
			ans[i-1]=min(ans[i-1],res[i][f]-h[f]);
		}

	}

	return ans;
}
 
/*int main(){
	
	ans=minimum_costs({2, 4, 3, 5}, {0, 1}, {2, 3});

	for(long long s:ans)cout<<s<<" ";
 
	return 0;
}*/

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:24:14: warning: overflow in conversion from 'long long int' to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
   24 |  h[0]=h[n+1]=inf;
      |              ^~~

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