#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
/*
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
*/
struct info
{
int l,r,av;
long long outp;
int left_child,right_child;
};
vector<info> tree;
vector<int> inp;
long long build(int node,int l,int r)
{
if(l>r)return 0;
int mx=0;
for(int j=l;j<=r;j++)
mx=max(mx,inp[j]);
vector<int> v={};
for(int j=l;j<=r;j++)
if(inp[j]==mx)v.push_back(j);
int cur=tree.size();
int av=v[v.size()/2];
info me;
me.l=l;
me.r=r;
me.av=av;
tree.push_back(me);
tree[node].left_child=node+1;
long long LHS=build(tree.size(),l,av-1)+1LL*mx*(r-av+1);
tree[node].right_child=tree.size();
long long RHS=build(tree.size(),av+1,r)+1LL*mx*(av-l+1);
tree[node].outp=min(LHS,RHS);
//cout<<l<<" "<<r<<" -> "<<tree[node].outp<<endl;
return min(LHS,RHS);
}
long long query(int node,int l,int r,int lq,int rq)
{
if(l>r||lq>rq)return 0;
if(l==lq&&r==rq)return tree[node].outp;
int av=tree[node].av;
if(rq<av)return query(tree[node].left_child,l,tree[node].av-1,lq,rq);
if(av<lq)return query(tree[node].right_child,tree[node].av+1,r,lq,rq);
long long LHS=query(tree[node].left_child,l,av-1,lq,av-1)+1LL*(rq-av+1)*inp[tree[node].av];
long long RHS=query(tree[node].right_child,av+1,r,av+1,rq)+1LL*(av-lq+1)*inp[tree[node].av];
return min(LHS,RHS);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
inp=H;
build(0,0,inp.size()-1);
vector<long long> outp={};
for(int i=0;i<L.size();i++)
outp.push_back(query(0,0,inp.size()-1,L[i],R[i]));
return outp;
}
/*
int main() {
int N = read_int();
int Q = read_int();
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
H[i] = read_int();
}
std::vector<int> L(Q), R(Q);
for (int j = 0; j < Q; ++j) {
L[j] = read_int();
R[j] = read_int();
}
std::vector<long long> C = minimum_costs(H, L, R);
for (size_t j = 0; j < C.size(); ++j) {
printf("%lld\n", C[j]);
}
return 0;
}
*/
Compilation message
meetings.cpp: In function 'long long int build(int, int, int)':
meetings.cpp:42:9: warning: unused variable 'cur' [-Wunused-variable]
42 | int cur=tree.size();
| ^~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:93:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i=0;i<L.size();i++)
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
2 ms |
492 KB |
Output is correct |
4 |
Correct |
2 ms |
588 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
2 ms |
560 KB |
Output is correct |
8 |
Correct |
3 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
2 ms |
492 KB |
Output is correct |
4 |
Correct |
2 ms |
588 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
2 ms |
560 KB |
Output is correct |
8 |
Correct |
3 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
6 ms |
844 KB |
Output is correct |
11 |
Correct |
5 ms |
844 KB |
Output is correct |
12 |
Correct |
6 ms |
844 KB |
Output is correct |
13 |
Correct |
6 ms |
844 KB |
Output is correct |
14 |
Correct |
5 ms |
940 KB |
Output is correct |
15 |
Correct |
6 ms |
816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
35 ms |
2760 KB |
Output is correct |
3 |
Correct |
121 ms |
9960 KB |
Output is correct |
4 |
Correct |
117 ms |
9944 KB |
Output is correct |
5 |
Correct |
97 ms |
9928 KB |
Output is correct |
6 |
Correct |
114 ms |
10040 KB |
Output is correct |
7 |
Correct |
124 ms |
10004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
35 ms |
2760 KB |
Output is correct |
3 |
Correct |
121 ms |
9960 KB |
Output is correct |
4 |
Correct |
117 ms |
9944 KB |
Output is correct |
5 |
Correct |
97 ms |
9928 KB |
Output is correct |
6 |
Correct |
114 ms |
10040 KB |
Output is correct |
7 |
Correct |
124 ms |
10004 KB |
Output is correct |
8 |
Correct |
117 ms |
9872 KB |
Output is correct |
9 |
Correct |
99 ms |
9912 KB |
Output is correct |
10 |
Correct |
112 ms |
9908 KB |
Output is correct |
11 |
Correct |
119 ms |
9976 KB |
Output is correct |
12 |
Correct |
103 ms |
9900 KB |
Output is correct |
13 |
Correct |
111 ms |
9876 KB |
Output is correct |
14 |
Correct |
115 ms |
9944 KB |
Output is correct |
15 |
Correct |
116 ms |
9900 KB |
Output is correct |
16 |
Correct |
273 ms |
10604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
2 ms |
492 KB |
Output is correct |
4 |
Correct |
2 ms |
588 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
2 ms |
560 KB |
Output is correct |
8 |
Correct |
3 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
6 ms |
844 KB |
Output is correct |
11 |
Correct |
5 ms |
844 KB |
Output is correct |
12 |
Correct |
6 ms |
844 KB |
Output is correct |
13 |
Correct |
6 ms |
844 KB |
Output is correct |
14 |
Correct |
5 ms |
940 KB |
Output is correct |
15 |
Correct |
6 ms |
816 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
35 ms |
2760 KB |
Output is correct |
18 |
Correct |
121 ms |
9960 KB |
Output is correct |
19 |
Correct |
117 ms |
9944 KB |
Output is correct |
20 |
Correct |
97 ms |
9928 KB |
Output is correct |
21 |
Correct |
114 ms |
10040 KB |
Output is correct |
22 |
Correct |
124 ms |
10004 KB |
Output is correct |
23 |
Correct |
117 ms |
9872 KB |
Output is correct |
24 |
Correct |
99 ms |
9912 KB |
Output is correct |
25 |
Correct |
112 ms |
9908 KB |
Output is correct |
26 |
Correct |
119 ms |
9976 KB |
Output is correct |
27 |
Correct |
103 ms |
9900 KB |
Output is correct |
28 |
Correct |
111 ms |
9876 KB |
Output is correct |
29 |
Correct |
115 ms |
9944 KB |
Output is correct |
30 |
Correct |
116 ms |
9900 KB |
Output is correct |
31 |
Correct |
273 ms |
10604 KB |
Output is correct |
32 |
Correct |
1540 ms |
80096 KB |
Output is correct |
33 |
Correct |
830 ms |
80360 KB |
Output is correct |
34 |
Correct |
1346 ms |
78088 KB |
Output is correct |
35 |
Correct |
1472 ms |
80124 KB |
Output is correct |
36 |
Correct |
842 ms |
80392 KB |
Output is correct |
37 |
Correct |
1296 ms |
78064 KB |
Output is correct |
38 |
Correct |
1301 ms |
80124 KB |
Output is correct |
39 |
Correct |
1335 ms |
80292 KB |
Output is correct |
40 |
Execution timed out |
5530 ms |
42064 KB |
Time limit exceeded |
41 |
Halted |
0 ms |
0 KB |
- |