oj.uz

Submission #624613

# Submission time Handle Problem Language Result Execution time Memory
624613 2022-08-08T14:41:29 Z prvocislo Meetings (IOI18_meetings) C++17
41 / 100
 229 ms 9204 KB 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "meetings.h"
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 1e5 + 5;
const int maxh = 21;
int n, q;
vector<int> h;
vector<int> o[maxh];
struct node
{
	int l, r;
	int nl, nr;
	ll ans;
	node()
	{
		l = -1, r = -1, nl = -1, nr = -1, ans = 0;
	}
} v[maxn];
int build(int l, int r) // vrati cislo vrchola kde sa postavil
{
	if (r < l) return n;
	int mx = -1;
	for (int i = maxh - 1; i >= 0; i--)
	{
		int lo = lower_bound(o[i].begin(), o[i].end(), l) - o[i].begin();
		if (lo != o[i].size() && o[i][lo] <= r)
		{
			int up = upper_bound(o[i].begin(), o[i].end(), r) - o[i].begin() - 1;
			mx = o[i][(lo + up) / 2];
			break;
		}
	}
	v[mx].l = l, v[mx].r = r;
	v[mx].nl = build(l, mx - 1), v[mx].nr = build(mx + 1, r);
	v[mx].ans = min((mx - l + 1) * 1ll * h[mx] + v[v[mx].nr].ans, (r - mx + 1) * 1ll * h[mx] + v[v[mx].nl].ans);
	return mx;
}
ll query(int l, int r, int vr)
{
	if (vr == n || r < v[vr].l || l > v[vr].r) 
		return 0;
	if (l <= v[vr].l && v[vr].r <= r) return v[vr].ans;
	if (r < vr) return query(l, r, v[vr].nl);
	if (l > vr) return query(l, r, v[vr].nr);
	ll ansl = query(l, r, v[vr].nl);
	ll ansr = query(l, r, v[vr].nr);
	return min(ansl + h[vr] * 1ll * (min(v[vr].r, r) - vr + 1), ansr + h[vr] * 1ll * (vr - max(v[vr].l, l) + 1));
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
	n = H.size();
	h = H;
	for (int i = 0; i < n; i++) o[h[i]].push_back(i);
	int root = build(0, n - 1);
	vector<ll> ans;
	for (int i = 0; i < L.size(); i++)
	{
		ans.push_back(query(L[i], R[i], root));
	}
	return ans;
}

Compilation message

meetings.cpp: In function 'int build(int, int)':
meetings.cpp:42:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   if (lo != o[i].size() && o[i][lo] <= r)
      |       ~~~^~~~~~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 0; i < L.size(); i++)
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5076 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5076 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 32 ms 4776 KB Output is correct
3 Correct 117 ms 8912 KB Output is correct
4 Correct 108 ms 8948 KB Output is correct
5 Correct 76 ms 8892 KB Output is correct
6 Correct 111 ms 8936 KB Output is correct
7 Correct 136 ms 8916 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 32 ms 4776 KB Output is correct
3 Correct 117 ms 8912 KB Output is correct
4 Correct 108 ms 8948 KB Output is correct
5 Correct 76 ms 8892 KB Output is correct
6 Correct 111 ms 8936 KB Output is correct
7 Correct 136 ms 8916 KB Output is correct
8 Correct 132 ms 9100 KB Output is correct
9 Correct 135 ms 9096 KB Output is correct
10 Correct 133 ms 9100 KB Output is correct
11 Correct 128 ms 9140 KB Output is correct
12 Correct 113 ms 9204 KB Output is correct
13 Correct 115 ms 9036 KB Output is correct
14 Correct 113 ms 9076 KB Output is correct
15 Correct 119 ms 8952 KB Output is correct
16 Correct 229 ms 9044 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5076 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -