oj.uz

Submission #1076304

# Submission time Handle Problem Language Result Execution time Memory
1076304 2024-08-26T12:43:05 Z 42kangaroo Meetings (IOI18_meetings) C++17
0 / 100
 385 ms 786432 KB 
//
// Created by 42kangaroo on 25/08/2024.
//
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

struct No {
	int l, r;
	ll miIn;
};

struct Node {
	No data;
	int l, r, hi, ind;
};

No comb(No l, int mi, No r) {
	if (l.miIn == -1) return {r.l - 1, r.r, r.miIn + mi};
	if (r.miIn == -1) return {l.l, l.r + 1, l.miIn + mi};
	return {l.l, r.r, min((ll)(l.r - l.l + 1)*mi + r.miIn, (ll)(r.r - r.l + 1)*mi + l.miIn)};
}

int construct(int l, int r, int h, vector<int>& ve, vector<Node>& out) {
	if (l == r) return 0;
	vector<int> inds;
	for (int i = l; i < r; ++i) {
		if (ve[i] == h) inds.push_back(i);
	}
	if (inds.empty()) return construct(l, r, h - 1, ve, out);
	int ind = out.size();
	out.push_back({{}, -1, -1, h, inds[inds.size()/2]});
	if (l + 1 == r) out.back().data = {l, r, h};
	else {
		out[ind].l = construct(l, inds[inds.size() / 2], h, ve, out);
		out[ind].r = construct(inds[inds.size() / 2] + 1, r, h, ve, out);
		out[ind].data = comb(out[out[ind].l].data, h, out[out[ind].r].data);
	}
	return ind;
}

No query(int l, int r, int i, vector<Node>& nos) {
	if (i == 0 || (r <= nos[i].data.l || nos[i].data.r <= l)) return nos[0].data;
	if (l <= nos[i].data.l && nos[i].data.r <= r) return nos[i].data;
	if (l + 1 == r && l == nos[i].ind) return {l, r, nos[i].hi};
	if (l > nos[i].ind) return query(l, r, nos[i].r, nos);
	if (r <= nos[i].ind) return query(l, r, nos[i].l, nos);
	assert(nos[i].l != 0 &&nos[i].r != 0);
	return comb(query(l, r, nos[i].l, nos), nos[i].hi, query(l, r, nos[i].r, nos));
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	vector<Node> nos{{-1, -1, -1}};
	construct(0, H.size(), 20, H, nos);
	vector<ll> res(L.size());
	for (int i = 0; i < L.size(); ++i) {
		res[i] = query(L[i], R[i] + 1, 1, nos).miIn;
	}
	return res;
}

Compilation message

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 385 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 385 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Runtime error 12 ms 4404 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Runtime error 12 ms 4404 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 385 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -