Submission #294576

#	Time	Username	Problem	Language	Result	Execution time	Memory
294576		SeDunion	Meetings (IOI18_meetings)	C++14	19 / 100	5588 ms	1572 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6;
ll p[N], s[N];

vector<ll> minimum_costs (vector<int> H, vector<int> L, vector<int> R) {
	int Q = L.size();
	vector<ll> C(Q);
	for (int query = 0 ; query < Q ; ++ query) {
		int l = L[query], r = R[query];
		{
			ll now = 0;
			map <int, ll> mp;
			for (int i = l ; i <= r ; ++ i) {
				mp[H[i]]++;
				now += H[i];
				while (mp.size()) {
					auto [key, val] = *mp.begin();
					if (key >= H[i]) break;
					mp.erase (mp.begin());
					now -= key * val;
					mp[H[i]] += val;
					now += H[i] * val;
				}
				p[i] = now;
			}
		}
		ll ans = p[r];
		p[l - 1] = 0;
		{
			ll now = 0;
			map <int, ll> mp;
			for (int i = r ; i >= l ; -- i) {
				mp[H[i]]++;
				now += H[i];
				while (mp.size()) {
					auto [key, val] = *mp.begin();
					if (key >= H[i]) break;
					mp.erase (mp.begin());
					now -= key * val;
					mp[H[i]] += val;
					now += H[i] * val;
				}
				ans = min (now + p[i - 1], ans);
			}
		}
		C[query] = ans;
	}
	return C;
}

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:21:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |      auto [key, val] = *mp.begin();
      |           ^
meetings.cpp:40:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |      auto [key, val] = *mp.begin();
      |           ^

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