Submission #379458

#	Time	Username	Problem	Language	Result	Execution time	Memory
379458		autumn_eel	Meetings (IOI18_meetings)	C++14	19 / 100	5545 ms	7740 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;

const ll INF=0x3f3f3f3f3f3f3f3f;

ll suml[800000],sumr[800000];
P st[800000];

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	int N=H.size(),Q=L.size();
	vector<ll>res;
	rep(i,Q){
		st[0]=P(INF,L[i]-1);
		ll sum=0;
		int p=1;
		for(int j=L[i];j<=R[i];j++){
			while(st[p-1].first<H[j]){
				sum-=(st[p-1].second-st[p-2].second)*st[p-1].first;
				p--;
			}
			sum+=(j-st[p-1].second)*H[j];
			suml[j]=sum;
			st[p++]=P(H[j],j);
		}
		st[0]=P(INF,R[i]+1);
		sum=0;
		p=1;
		for(int j=R[i];j>=L[i];j--){
			while(st[p-1].first<H[j]){
				sum-=(st[p-2].second-st[p-1].second)*st[p-1].first;
				p--;
			}
			sum+=(st[p-1].second-j)*H[j];
			sumr[j]=sum;
			st[p++]=P(H[j],j);
		}
		ll ans=INF;
		for(int j=L[i];j<=R[i];j++){
			ans=min(ans,suml[j]+sumr[j]-H[j]);
		}
		res.push_back(ans);
	}
	return res;
}

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:15:6: warning: unused variable 'N' [-Wunused-variable]
   15 |  int N=H.size(),Q=L.size();
      |      ^

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