Submission #1075081

#TimeUsernameProblemLanguageResultExecution timeMemory
107508142kangarooMeetings (IOI18_meetings)C++17
0 / 100
412 ms786432 KiB
// // 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; if (r.miIn == -1) return l; if (l.l > r.l) swap(l, r); return {l.l, r.r, min((l.r - l.l + 1)*mi + r.miIn, (r.r - l.r + 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]}); 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 (r <= nos[i].l || nos[i].r <= l) return nos[0].data; if (l <= nos[i].l && nos[i].r < r) return nos[i].data; 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); 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 (stderr)

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