#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 750005;
const int maxv = 25;
int arr[maxn];
int n, q;
vector<int> buck[maxv];
struct segtree
{
int sz;
struct node
{
ll val;
node *left, *right;
node(ll _val = 0, node* _left = NULL, node* _right = NULL)
{
val = _val; left = _left; right = _right;
}
node* build(vector<ll> &vals, int L, int R)
{
if(L == R)
{
return new node(vals[L], NULL, NULL);
}
int M = (L+R)/2;
node* x = build(vals, L, M);
node* y = build(vals, M+1, R);
return new node(min(x->val, y->val), x, y);
}
ll ask(int i, int j, int L, int R)
{
if(i> R || j< L) return 4e18;
if(i<= L && R<= j) return val;
int M = (L+R)/2;
ll x = left->ask(i, j, L, M);
ll y = right->ask(i, j, M+1, R);
return min(x, y);
}
};
node *root;
segtree(){}
segtree(vector<ll> &vals)
{
sz = vals.size();
root = root->build(vals, 0, sz-1);
}
ll ask(int i, int j)
{
return root->ask(i, j, 0, sz-1);
}
};
struct cart
{
ll val;
vector<cart*> ptr; //size k+1
vector<int> poles; //size k
vector<ll> cand; //size k+1
segtree seg;
cart(){}
cart(int L, int R, int H)
{
if(L> R)
{
val = 0;
return;
}
int lo = lower_bound(buck[H].begin(), buck[H].end(), L)-buck[H].begin();
int hi = upper_bound(buck[H].begin(), buck[H].end(), R)-buck[H].begin()-1;
for(int i = lo; i<= hi; i++)
{
poles.pb(buck[H][i]);
}
ptr.resize(poles.size()+1);
cand.resize(poles.size()+1);
for(int i = 0; i< (int) ptr.size(); i++)
{
int sai = (i?poles[i-1]+1:L);
int kwa = (i< poles.size()?poles[i]-1:R);
// printf("[%d %d] %d (%d)to [%d %d] %d\n", L, R, H, i, sai, kwa, H-1);
ptr[i] = new cart(sai, kwa, H-1);
cand[i] = ptr[i]->val;
cand[i] -= 1LL*(kwa-sai+1)*H;
}
seg = segtree(cand);
val = min(seg.ask(0, seg.sz-1)+1LL*(R-L+1)*H, 1LL*(R-L+1)*H);
// printf("[%d %d] %d = %lld\n", L, R, H, val);
}
ll ask(int i, int j, int L = 0, int R = n-1, int H = 21)
{
if(L> R|| i> R || j< L) return 0;
// printf("asking %d %d %d\n", L, R, H);
if(i<= L && R<= j)
{
// printf("= %lld\n", val);
return val;
}
int sai = lower_bound(poles.begin(), poles.end(), i)-poles.begin();
int kwa = upper_bound(poles.begin(), poles.end(), j)-poles.begin()-1;
if(sai> kwa)
{
int tahm = (sai?poles[sai-1]+1:L);
int kench = (sai< poles.size()?poles[sai]-1:R);
return ptr[sai]->ask(i, j, tahm, kench, H-1);
}
// if(sai == kwa) printf("sai = kwa! [%d]\n", poles[sai]);
// printf("for [%d %d]\n", L, R);
ll x = ptr[sai]->ask(i, poles[sai]-1, sai?poles[sai-1]+1:L, poles[sai]-1, H-1)-1LL*(poles[sai]-i)*H;
// printf("x = %lld\n", x);
ll mid = seg.ask(sai+1, kwa);
ll y = ptr[kwa+1]->ask(poles[kwa]+1, j, poles[kwa]+1, kwa+1<poles.size()?poles[kwa+1]-1:R, H-1)-1LL*(j-poles[kwa])*H;
// printf("y = %lld\n", y);
return min(min(0LL, mid), min(x, y)) + 1LL*(j-i+1)*H;
}
};
cart foo;
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
n = H.size(); q = L.size();
for(int i = 0; i< n; i++) arr[i] = H[i];
for(int i = 0; i< n; i++)
{
buck[arr[i]].pb(i);
}
foo = cart(0, n-1, 21);
vector<ll> ans(q);
for(int i = 0; i< q; i++)
{
ans[i] = foo.ask(L[i], R[i]);
assert(ans[i]> 0);
}
return ans;
}
Compilation message
meetings.cpp: In constructor 'cart::cart(int, int, int)':
meetings.cpp:90:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
int kwa = (i< poles.size()?poles[i]-1:R);
~^~~~~~~~~~~~~~
meetings.cpp: In member function 'll cart::ask(int, int, int, int, int)':
meetings.cpp:115:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
int kench = (sai< poles.size()?poles[sai]-1:R);
~~~^~~~~~~~~~~~~~
meetings.cpp:123:62: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
ll y = ptr[kwa+1]->ask(poles[kwa]+1, j, poles[kwa]+1, kwa+1<poles.size()?poles[kwa+1]-1:R, H-1)-1LL*(j-poles[kwa])*H;
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
63 ms |
3704 KB |
Output is correct |
| 3 |
Correct |
249 ms |
28620 KB |
Output is correct |
| 4 |
Correct |
257 ms |
23568 KB |
Output is correct |
| 5 |
Correct |
173 ms |
28596 KB |
Output is correct |
| 6 |
Correct |
228 ms |
23512 KB |
Output is correct |
| 7 |
Correct |
250 ms |
23564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
63 ms |
3704 KB |
Output is correct |
| 3 |
Correct |
249 ms |
28620 KB |
Output is correct |
| 4 |
Correct |
257 ms |
23568 KB |
Output is correct |
| 5 |
Correct |
173 ms |
28596 KB |
Output is correct |
| 6 |
Correct |
228 ms |
23512 KB |
Output is correct |
| 7 |
Correct |
250 ms |
23564 KB |
Output is correct |
| 8 |
Correct |
484 ms |
91984 KB |
Output is correct |
| 9 |
Correct |
281 ms |
91920 KB |
Output is correct |
| 10 |
Correct |
498 ms |
92024 KB |
Output is correct |
| 11 |
Correct |
488 ms |
88800 KB |
Output is correct |
| 12 |
Correct |
281 ms |
88540 KB |
Output is correct |
| 13 |
Correct |
508 ms |
88808 KB |
Output is correct |
| 14 |
Correct |
375 ms |
126004 KB |
Output is correct |
| 15 |
Correct |
360 ms |
55568 KB |
Output is correct |
| 16 |
Correct |
424 ms |
23672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
