| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 944772 |
2024-03-13T04:38:06 Z |
salmon |
Meetings (IOI18_meetings) |
C++14 |
|
5500 ms |
298152 KB |
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
int N;
int Q;
int lst[250100];
long long int num[200100][25];
pair<int,int> st[500100];
pair<int,int> st1[500100];
void build(int i, int s, int e){
if(s == e){
st[i] = {lst[s],s};
st1[i] = {lst[s],-s};
return;
}
int m = (s + e)/2;
build(i * 2,s,m);
build(i * 2 + 1, m + 1, e);
st[i] = max(st[i * 2],st[i * 2 + 1]);
st1[i] = max(st1[i * 2],st1[i * 2 + 1]);
}
pair<int,int> query(int i, int s, int e, int S, int E){
if(S <= s && e <= E){
return st[i];
}
int m = (s + e)/2;
if(S <= m && m < E){
return max(query(i*2,s,m,S,E), query(i*2+1,m+1,e,S,E));
}
if(S <= m) return query(i * 2, s, m ,S, E);
if(m < E) return query(i * 2 + 1, m + 1, e, S, E);
}
pair<int,int> query1(int i, int s, int e, int S, int E){
if(S <= s && e <= E){
return st1[i];
}
int m = (s + e)/2;
if(S <= m && m < E){
return max(query1(i*2,s,m,S,E), query1(i*2+1,m+1,e,S,E));
}
if(S <= m) return query1(i * 2, s, m ,S, E);
if(m < E) return query1(i * 2 + 1, m + 1, e, S, E);
}
long long int recurse(int j, int l ,int r){
if(l > r) return 0;
if(l == r && lst[l] == j){
num[l][j] = 0;
return j;
}
long long int small = 1e18;
vector<int> temp = {l - 1};
for(int i = l; i <= r; i++){
if(lst[i] == j) temp.push_back(i);
}
temp.push_back(r + 1);
for(int i = 0; i < temp.size() - 1; i++){
long long int vum = recurse(j - 1,temp[i] + 1, temp[i + 1] - 1) + (temp[i] - l + 1 + r - temp[i + 1] + 1) * j;
small = min(small, vum);
num[temp[i + 1] - 1][j] = vum - (r - l + 1) * j;
}
return small;
}
struct node{
int s, e, m;
node *l, *r;
long long int v;
int j;
node(int S, int E, int J){
s = S;
e = E;
m = (s + e)/2;
j = J;
if(s == e){
v = num[s][j];
}
else{
l = new node(s,m,J);
r = new node(m + 1, e,J);
v = min(l -> v, r -> v);
}
}
long long int query(int S, int E){
if(S <= s && e <= E) return v;
long long int V = 1e18;
if(S <= m){
V = min(V , l -> query(S,E));
}
if(m < E){
V = min(V, r -> query(S,E));
}
return V;
}
} *nodes[25];
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
N = H.size();
Q = L.size();
if(N >= 5000){
for(int i = 1; i <= N; i++){
lst[i] = H[i - 1];
}
for(int i = 0; i <= N; i++){
for(int j = 0; j <= 20; j++){
num[i][j] = 1e18;
}
}
recurse(20,1,N);
for(int j = 0; j <= 20; j++){
nodes[j] = new node(1,N,j);
}
/*for(int j = 0; j <= 20; j++){
for(int i = 1 ; i <= N; i++){
printf("%d ",num[i][j]);
}
printf("\n");
}*/
build(1,1,N);
vector<long long int> banna;
for(int i = 0; i < Q; i++){
vector<vector<long long int>> v1;
v1.push_back({0,L[i]+1,R[i]+1,0});
long long int ans = 1e18;
long long int cont = 20;
while(cont >= 0){
vector<vector<long long int>> temp;
//printf("%d %d\n",ans,cont);
while(!v1.empty()){
vector<long long int> v = v1.back();
v1.pop_back();
//printf("%d %d %d %d\n",v[0],v[1],v[2],v[3]);
long long int k = ans;
pair<int,int> p = query(1,1,N,v[1],v[2]);
if(p.first != cont){
temp.push_back(v);
continue;
}
if(v[2] == v[1]){
ans = min(ans, cont + v[0]);
continue;
}
pair<int,int> p1 = query1(1,1,N,v[1],v[2]);
ans = min(ans, p1.first * (v[2] - v[1] + 1));
if(v[3] == 0){
if(p.second == -p1.second){
int it = p.second;
if(it != v[1]){
temp.push_back({v[0] + cont * (v[2] - it + 1), v[1], it - 1,2});
}
if(it != v[2]){
temp.push_back({v[0] + cont * (it - v[1] + 1), it + 1, v[2],1});
}
}
else{
int it = -p1.second;
int it1 = p.second;
if(it != v[1]){
temp.push_back({v[0] + cont * (v[2] - it + 1), v[1], it - 1, 2});
}
if(it1 != v[2]){
temp.push_back({v[0] + cont * (it1 - v[1] + 1), it1 + 1, v[2],1});
}
ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(it + 1, it1));
}
}
else if(v[3] == 1){
if(p.second == -p1.second){
int it = p.second;
if(it != v[1]){
ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(it - 1,it - 1));
}
if(it != v[2]){
temp.push_back({v[0] + cont * (it - v[1] + 1), it + 1, v[2],1});
}
}
else{
int it = -p1.second;
int it1 = p.second;
if(it != v[1]){
ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(it - 1,it - 1));
}
if(it1 != v[2]){
temp.push_back({v[0] + cont * (it1 - v[1] + 1), it1 + 1, v[2],1});
}
ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(it + 1, it1));
}
}
else{
if(p.second == -p1.second){
int it = p.second;
if(it != v[1]){
temp.push_back({v[0] + cont * (v[2] - it + 1), v[1], it - 1,2});
}
if(it != v[2]){
ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(v[2],v[2]));
}
}
else{
int it = -p1.second;
int it1 = p.second;
if(it != v[1]){
temp.push_back({v[0] + cont * (v[2] - it + 1), v[1], it - 1, 2});
}
if(it1 != v[2]){
ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(v[2],v[2]));
}
ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(it + 1, it1));
}
}
ans = min(ans + v[0],k);
}
v1 = temp;
cont--;
}
banna.push_back(ans);
}
return banna;
}
else{
for(int i = 0; i < N; i++){
lst[i] = H[i];
}
build(1,0,N-1);
vector<long long int> banna;
for(int i = 0; i < Q; i++){
int l,r;
l = L[i];
r = R[i];
queue<vector<long long int>> pq;
pq.push({0,l,r});
long long int ans = 1e18;
while(!pq.empty()){
vector<long long int> v = pq.front();
pq.pop();
if(v[1] == v[2]){
ans = min(ans, v[0] + lst[v[1]]);
continue;
}
int it = query(1,0,N-1,v[1],v[2]).second;
if(it != v[1]){
pq.push({lst[it] * (v[2] - it + 1) + v[0], v[1], it - 1 });
}
if(it != v[2]){
pq.push({lst[it] * (it - v[1] + 1) + v[0], it + 1, v[2] });
}
}
banna.push_back(ans);
}
return banna;
}
}
Compilation message
meetings.cpp: In function 'long long int recurse(int, int, int)':
meetings.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i = 0; i < temp.size() - 1; i++){
| ~~^~~~~~~~~~~~~~~~~
meetings.cpp: In function 'std::pair<int, int> query(int, int, int, int, int)':
meetings.cpp:42:1: warning: control reaches end of non-void function [-Wreturn-type]
42 | }
| ^
meetings.cpp: In function 'std::pair<int, int> query1(int, int, int, int, int)':
meetings.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
57 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4440 KB |
Output is correct |
| 3 |
Correct |
5 ms |
4632 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4688 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4472 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
5 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4440 KB |
Output is correct |
| 3 |
Correct |
5 ms |
4632 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4688 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4472 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
5 ms |
4444 KB |
Output is correct |
| 10 |
Execution timed out |
5522 ms |
83164 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
237 ms |
31276 KB |
Output is correct |
| 3 |
Correct |
886 ms |
297848 KB |
Output is correct |
| 4 |
Correct |
1053 ms |
297844 KB |
Output is correct |
| 5 |
Correct |
494 ms |
297788 KB |
Output is correct |
| 6 |
Correct |
736 ms |
297820 KB |
Output is correct |
| 7 |
Correct |
820 ms |
298152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
237 ms |
31276 KB |
Output is correct |
| 3 |
Correct |
886 ms |
297848 KB |
Output is correct |
| 4 |
Correct |
1053 ms |
297844 KB |
Output is correct |
| 5 |
Correct |
494 ms |
297788 KB |
Output is correct |
| 6 |
Correct |
736 ms |
297820 KB |
Output is correct |
| 7 |
Correct |
820 ms |
298152 KB |
Output is correct |
| 8 |
Correct |
1256 ms |
298032 KB |
Output is correct |
| 9 |
Correct |
734 ms |
297852 KB |
Output is correct |
| 10 |
Correct |
1135 ms |
297944 KB |
Output is correct |
| 11 |
Correct |
1375 ms |
297984 KB |
Output is correct |
| 12 |
Correct |
861 ms |
297680 KB |
Output is correct |
| 13 |
Correct |
1219 ms |
297752 KB |
Output is correct |
| 14 |
Correct |
569 ms |
297904 KB |
Output is correct |
| 15 |
Correct |
2011 ms |
298028 KB |
Output is correct |
| 16 |
Correct |
979 ms |
297776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4440 KB |
Output is correct |
| 3 |
Correct |
5 ms |
4632 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4688 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4472 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
5 ms |
4444 KB |
Output is correct |
| 10 |
Execution timed out |
5522 ms |
83164 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
