Submission #295841

#	Time	Username	Problem	Language	Result	Execution time	Memory
295841		Dovran	Meetings (IOI18_meetings)	C++11	0 / 100	5098 ms	2884 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
#define N 800009
#define LL 1000000009
#define ll long long
#define pii pair <ll, ll>
#define ff first
#define ss second
#define sz() size()
#define pb push_back

using namespace std;

ll n, c[N];
pii a[N];
vector<pii>e;
vector<ll>ans;

std::vector<ll> minimum_costs(std::vector<int>v, std::vector<int>L, std::vector<int>R){
	n=v.sz();
	
	
	for(int i=0; i<L.sz(); i++){
		int l=L[i], r=R[i];
		
		for(int j=0; j<n; j++) a[j]={l-1, r+1}, c[j]=0;
		
		for(int j=l; j<=r; j++){
			while(!e.empty()){
				int sz=e.sz()-1;
				if(e[sz].ff>v[j]){
					a[j].ff=e[sz].ss;
					break;
				}
//				a[e[sz].ss].ss=j;
				e.pop_back();
			}
			e.pb({v[j], j});
		}
		e.clear();
		for(int j=r; j>=l; j--){
			while(!e.empty()){
				int sz=e.sz()-1;
				if(e[sz].ff>v[j]){
					a[j].ss=e[sz].ss;
					break;
				}
//				a[e[sz].ss].ff=j;
				e.pop_back();
			}
			e.pb({v[j], j});
		}
		
//		for(int j=l; j<=r; j++)
//			cout<<j<<" -- "<<a[j].ff<<' '<<a[j].ss<<'\n';
//		cout<<'\n';
		for(int j=l; j<=r; j++){
			ll x=j-a[j].ff, y=a[j].ss-j;
			c[a[j].ff+1]+=v[j]*y;
			c[j]-=v[j]*y;
			
			c[j+1]+=v[j]*x;
			c[a[j].ss]-=v[j]*x;
			
			c[j]+=(a[j].ss-a[j].ff-1)*v[j];
			c[j+1]-=(a[j].ss-a[j].ff-1)*v[j];
		
		}
		
		ll mn=1e18;
		for(int j=l-1; j<=r+1; j++)
			c[j]+=c[j-1];
//		cout<<'\n';
		for(int j=l; j<=r; j++)
			mn=min(mn, (c[j]));
		
//		cout<<"------\n";
		ans.pb(mn);
	}
	return ans;
}
/*
int main(){
	int M, q;
	vector<int>H, A, B;
	cin>>M>>q;
	for(int i=0; i<M; i++){
		int X;
		cin>>X;
		H.pb(X);
	}
	for(int i=0; i<q; i++){
		int X, Y;
		cin>>X>>Y;
		A.pb(X), B.pb(Y);
	}
	vector<ll>e=minimum_costs(H, A, B);
	for(auto i:e)
		cout<<i<<' ';
}*/

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:23:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i=0; i<L.sz(); i++){
      |                ^

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