Submission #778834

#	Time	Username	Problem	Language	Result	Execution time	Memory
778834		amunduzbaev	Meetings (IOI18_meetings)	C++17	19 / 100	505 ms	2132 KiB

meetings

#include "meetings.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;
typedef int32_t ii;

vector<ll> minimum_costs(vector<int> a, vector<int> l, vector<int> r) {
	int n = a.size(), q = l.size();
	
	if(n <= 5000 && q <= 5000){
		vector<ll> res(q);
		
		auto get = [&](vector<int> a){
			int n = a.size();
			ll cur = 0;
			vector<int> ss;
			vector<ll> cost(n);
			for(int i=0;i<n;i++){
				while(!ss.empty() && a[ss.back()] <= a[i]){
					int id = ss.back();
					ss.pop_back();
					if(ss.empty()) cur -= a[id] * 1ll * (id + 1);
					else cur -= a[id] * 1ll * (id - ss.back());
				}
				
				if(ss.empty()) cur += a[i] * 1ll * (i + 1);
				else cur += a[i] * 1ll * (i - ss.back());
				ss.push_back(i);
				cost[i] += cur;
			}
			
			ss.clear(); cur = 0;
			for(int i= n - 1;~i;i--){
				while(!ss.empty() && a[ss.back()] <= a[i]){
					int id = ss.back();
					ss.pop_back();
					if(ss.empty()) cur -= a[id] * 1ll * (n - id);
					else cur -= a[id] * 1ll * (ss.back() - id);
				}
				
				if(ss.empty()) cur += a[i] * 1ll * (n - i);
				else cur += a[i] * 1ll * (ss.back() - i);
				ss.push_back(i);
				cost[i] += cur;
			}
			
			ll mn = 1e18;
			for(int i=0;i<n;i++){
				mn = min(mn, cost[i] - a[i]);
			}
			
			return mn;
		};
		
		for(int i=0;i<q;i++){
			vector<int> b;
			for(int j=l[i];j<=r[i];j++){
				b.push_back(a[j]);
			}
			
			res[i] = get(b);
		}
		
		return res;
	}
	
	assert(false);
	vector<ll> res(q);
	return res;
}

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