# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
429385 |
2021-06-15T22:18:19 Z |
peuch |
Meetings (IOI18_meetings) |
C++17 |
|
5500 ms |
2764 KB |
#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int bSize;
struct node{
long long val, lzVal;
node (long long _val = INF, long long _lzVal = 0){
val = _val, lzVal = _lzVal;
}
node operator + (node a){
return node(min(val, a.val));
}
};
struct query{
int l, r, id;
query (int _l = 0, int _r = 0, int _id = 0){
l = _l, r = _r, id = _id;
}
bool operator < (query a){
if(l / bSize == a.l / bSize) return r < a.r;
return l < a.l;
}
};
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
bSize = sqrt(H.size());
vector<query> qry (L.size());
vector<long long> ans (L.size());
for(int i = 0; i < L.size(); i++){
int a = L[i];
int b = R[i];
ans[i] = INF;
for(int j = a; j <= b; j++){
long long sum = H[j];
long long maxi = H[j];
for(int k = j + 1; k <= b; k++){
maxi = max(maxi, (long long)H[k]);
sum += maxi;
}
maxi = H[j];
for(int k = j - 1; k >= a; k--){
maxi = max(maxi, (long long)H[k]);
sum += maxi;
}
ans[i] = min(ans[i], sum);
}
}
// for(int i = 0; i < L.size(); i++)
// qry[i] = query(L[i], R[i], i);
// sort(qry.begin(), qry.end());
//
// int ini = 0;
// int fim = -1;
// for(int i = 0; i < qry.size(); i++){
// int l = qry[i].l;
// int r = qry[i].r;
// int id = qry[i].id;
// while(fim > r){
// tira(fim);
// fim--;
// }
// while(fim < r){
// fim++;
// add(fim);
// }
// while(ini < l){
// tira(ini);
// ini++;
// }
// while(ini > l){
// ini--;
// add(ini);
// }
// ans[id] = seg[1].val;
// }
return ans;
}
Compilation message
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | 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 |
18 ms |
332 KB |
Output is correct |
3 |
Correct |
126 ms |
332 KB |
Output is correct |
4 |
Correct |
42 ms |
332 KB |
Output is correct |
5 |
Correct |
118 ms |
332 KB |
Output is correct |
6 |
Correct |
12 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
5 ms |
332 KB |
Output is correct |
9 |
Correct |
117 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
18 ms |
332 KB |
Output is correct |
3 |
Correct |
126 ms |
332 KB |
Output is correct |
4 |
Correct |
42 ms |
332 KB |
Output is correct |
5 |
Correct |
118 ms |
332 KB |
Output is correct |
6 |
Correct |
12 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
5 ms |
332 KB |
Output is correct |
9 |
Correct |
117 ms |
308 KB |
Output is correct |
10 |
Execution timed out |
5586 ms |
548 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Execution timed out |
5596 ms |
2764 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Execution timed out |
5596 ms |
2764 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
18 ms |
332 KB |
Output is correct |
3 |
Correct |
126 ms |
332 KB |
Output is correct |
4 |
Correct |
42 ms |
332 KB |
Output is correct |
5 |
Correct |
118 ms |
332 KB |
Output is correct |
6 |
Correct |
12 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
5 ms |
332 KB |
Output is correct |
9 |
Correct |
117 ms |
308 KB |
Output is correct |
10 |
Execution timed out |
5586 ms |
548 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |