Submission #1105505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105505		alexander707070	Meetings (IOI18_meetings)	C++14	19 / 100	5561 ms	25532 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<long long> ans;

int dp[MAXN][20],power[20],lg[MAXN];

int best(int x,int y){
	if(h[x]>=h[y])return x;
	return y;
}

void calcdp(){
	power[0]=1;
	for(int i=1;i<20;i++)power[i]=power[i-1]*2;
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;

	for(int i=1;i<=n;i++)dp[i][0]=i;

	for(int j=1;j<20;j++){
		for(int i=1;i+power[j]-1<=n;i++){
			dp[i][j]=best(dp[i][j-1],dp[i+power[j-1]][j-1]);
		}
	}
}

int getmax(int l,int r){
	if(l>r)return 0;
	return best( dp[l][lg[r-l+1]] , dp[r-power[lg[r-l+1]]+1][lg[r-l+1]] );
}

unordered_map<long long,long long> res;

long long id(long long l,long long r){
	return l*1000000+r;
}

long long solve(int l,int r){
	if(l>r)return 0;

	if(res[id(l,r)]!=0)return res[id(l,r)];

	long long s=inf,val=h[getmax(l,r)];

	vector<int> pos={l-1};
	int x=l;
	while(true){
		x=getmax(x,r);
		if(h[x]!=val)break;

		pos.push_back(x);
		x++;
	}

	pos.push_back(r+1);
	for(int i=1;i<pos.size();i++){
		s=min(s, solve(pos[i-1]+1,pos[i]-1) + val*(r-l+1-(pos[i]-pos[i-1]-1)) );
	}

	res[id(l,r)]=s;
	return s;
}

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];
	}
	calcdp();

	for(int i=1;i<=q;i++){
		ans.push_back(solve(L[i-1]+1,R[i-1]+1));
	}

	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 'long long int solve(int, int)':
meetings.cpp:64:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i=1;i<pos.size();i++){
      |              ~^~~~~~~~~~~

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