# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
390812 |
2021-04-17T03:43:24 Z |
tinjyu |
Meetings (IOI18_meetings) |
C++14 |
|
846 ms |
216040 KB |
#include "meetings.h"
#include <iostream>
using namespace std;
long long int point[5005][5005][2],tree[1000005][3],he[1000005],len[1000005],temp[1000005][3],st,en;
int build(int s,int e,int t)
{
if(s==e)
{
if(he[s]==1)
{
tree[t][0]=1;
tree[t][1]=1;
tree[t][2]=1;
}
return 0;
}
else
{
build(s,(s+e)/2,t*2);
build((s+e)/2+1,e,t*2+1);
tree[t][0]=max(tree[t*2][0],max(tree[t*2+1][0],tree[t*2][2]+tree[t*2+1][1]));
if(tree[t*2][1]==(s+e)/2-s+1)
{
tree[t][1]=tree[t*2][1]+tree[t*2+1][1];
}
else tree[t][1]=tree[t*2][1];
if(tree[t*2+1][2]==e-(s+e)/2)
{
tree[t][2]=tree[t*2][2]+tree[t*2+1][2];
}
else tree[t][2]=tree[t*2+1][2];
}
return 0;
}
int find(int s,int e,int t)
{
if(e<st || s>en)
{
temp[t][0]=0;
temp[t][1]=0;
temp[t][2]=0;
len[t]=1;
return 0;
}
if(st<=s && e<=en)
{
temp[t][0]=tree[t][0];
temp[t][1]=tree[t][1];
temp[t][2]=tree[t][2];
len[t]=e-s+1;
return 0;
}
find(s,(s+e)/2,t*2);
find((s+e)/2+1,e,t*2+1);
len[t]=len[t*2]+len[t*2+1];
temp[t][0]=max(temp[t*2][0],max(temp[t*2+1][0],temp[t*2][2]+temp[t*2+1][1]));
if(temp[t*2][1]==len[t*2])
{
temp[t][1]=temp[t*2][1]+temp[t*2+1][1];
}
else temp[t][1]=temp[t*2][1];
if(temp[t*2+1][2]==len[t*2+1])
{
temp[t][2]=temp[t*2][2]+temp[t*2+1][2];
}
else temp[t][2]=temp[t*2+1][2];
return 0;
}
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l, std::vector<int> r) {
int q = l.size();
int n = h.size();
if(n<=5000 && q<=5000)
{
for(int i=0;i<n;i++)
{
int tmp=h[i];
point[i][i][1]=h[i];
for(int j=i+1;j<n;j++)
{
tmp=max(tmp,h[j]);
point[i][j][1]=point[i][j-1][1]+tmp;
}
}
for(int i=n-1;i>=0;i--)
{
int tmp=h[i];
point[i][i][0]=h[i];
for(int j=i-1;j>=0;j--)
{
tmp=max(tmp,h[j]);
point[j][i][0]=point[j+1][i][0]+tmp;
//cout<<i<<" "<<j<<" "<<point[j][i][0]<<" ";
}
//cout<<endl;
}
std::vector<long long> c(q);
for(int i=0;i<q;i++)
{
long long int tmp=999999999999999999;
for(int j=l[i];j<=r[i];j++)
{
if(point[l[i]][j][0]+point[j][r[i]][1]-h[j]<tmp)
{
c[i]=j;
tmp=point[l[i]][j][0]+point[j][r[i]][1]-h[j];
//cout<<tmp<<" "<<j<<" "<<point[l[i]][j][0]<<" "<<point[j][r[i]][1]<<" ";
}
}
c[i]=tmp;
//cout<<endl;
}
return c;
}
else
{
//cout<<"ok"<<endl;
for(int i=0;i<n;i++)he[i]=h[i];
build(0,n-1,1);
//cout<<"ok"<<endl;
std::vector<long long> c(q);
for(int i=0;i<q;i++)
{
st=l[i],en=r[i];
long long int len=0,now=0;
find(0,n-1,1);
c[i]=(r[i]-l[i]+1)*2-temp[1][0];
}
return c;
}
}
Compilation message
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:125:18: warning: unused variable 'len' [-Wunused-variable]
125 | long long int len=0,now=0;
| ^~~
meetings.cpp:125:24: warning: unused variable 'now' [-Wunused-variable]
125 | long long int len=0,now=0;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
103 ms |
83020 KB |
Output is correct |
3 |
Correct |
102 ms |
82960 KB |
Output is correct |
4 |
Correct |
102 ms |
82976 KB |
Output is correct |
5 |
Correct |
103 ms |
83012 KB |
Output is correct |
6 |
Correct |
104 ms |
82956 KB |
Output is correct |
7 |
Correct |
101 ms |
83028 KB |
Output is correct |
8 |
Correct |
101 ms |
83028 KB |
Output is correct |
9 |
Correct |
104 ms |
83020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
103 ms |
83020 KB |
Output is correct |
3 |
Correct |
102 ms |
82960 KB |
Output is correct |
4 |
Correct |
102 ms |
82976 KB |
Output is correct |
5 |
Correct |
103 ms |
83012 KB |
Output is correct |
6 |
Correct |
104 ms |
82956 KB |
Output is correct |
7 |
Correct |
101 ms |
83028 KB |
Output is correct |
8 |
Correct |
101 ms |
83028 KB |
Output is correct |
9 |
Correct |
104 ms |
83020 KB |
Output is correct |
10 |
Correct |
512 ms |
215912 KB |
Output is correct |
11 |
Correct |
842 ms |
215996 KB |
Output is correct |
12 |
Correct |
491 ms |
216040 KB |
Output is correct |
13 |
Correct |
846 ms |
216004 KB |
Output is correct |
14 |
Correct |
509 ms |
216036 KB |
Output is correct |
15 |
Correct |
503 ms |
215912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
52 ms |
2628 KB |
Output is correct |
3 |
Correct |
181 ms |
18608 KB |
Output is correct |
4 |
Correct |
188 ms |
20552 KB |
Output is correct |
5 |
Correct |
144 ms |
20524 KB |
Output is correct |
6 |
Correct |
157 ms |
18992 KB |
Output is correct |
7 |
Correct |
178 ms |
19080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
52 ms |
2628 KB |
Output is correct |
3 |
Correct |
181 ms |
18608 KB |
Output is correct |
4 |
Correct |
188 ms |
20552 KB |
Output is correct |
5 |
Correct |
144 ms |
20524 KB |
Output is correct |
6 |
Correct |
157 ms |
18992 KB |
Output is correct |
7 |
Correct |
178 ms |
19080 KB |
Output is correct |
8 |
Incorrect |
189 ms |
20780 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
103 ms |
83020 KB |
Output is correct |
3 |
Correct |
102 ms |
82960 KB |
Output is correct |
4 |
Correct |
102 ms |
82976 KB |
Output is correct |
5 |
Correct |
103 ms |
83012 KB |
Output is correct |
6 |
Correct |
104 ms |
82956 KB |
Output is correct |
7 |
Correct |
101 ms |
83028 KB |
Output is correct |
8 |
Correct |
101 ms |
83028 KB |
Output is correct |
9 |
Correct |
104 ms |
83020 KB |
Output is correct |
10 |
Correct |
512 ms |
215912 KB |
Output is correct |
11 |
Correct |
842 ms |
215996 KB |
Output is correct |
12 |
Correct |
491 ms |
216040 KB |
Output is correct |
13 |
Correct |
846 ms |
216004 KB |
Output is correct |
14 |
Correct |
509 ms |
216036 KB |
Output is correct |
15 |
Correct |
503 ms |
215912 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
52 ms |
2628 KB |
Output is correct |
18 |
Correct |
181 ms |
18608 KB |
Output is correct |
19 |
Correct |
188 ms |
20552 KB |
Output is correct |
20 |
Correct |
144 ms |
20524 KB |
Output is correct |
21 |
Correct |
157 ms |
18992 KB |
Output is correct |
22 |
Correct |
178 ms |
19080 KB |
Output is correct |
23 |
Incorrect |
189 ms |
20780 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |