Submission #390806

#TimeUsernameProblemLanguageResultExecution timeMemory
390806tinjyuMeetings (IOI18_meetings)C++14
19 / 100
798 ms216136 KiB
#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]; } } 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]; } 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 { build(0,n-1,1); for(int i=0;i<n;i++)he[i]=h[i]; 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 (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:121:18: warning: unused variable 'len' [-Wunused-variable]
  121 |    long long int len=0,now=0;
      |                  ^~~
meetings.cpp:121:24: warning: unused variable 'now' [-Wunused-variable]
  121 |    long long int len=0,now=0;
      |                        ^~~
meetings.cpp: In function 'int build(int, int, int)':
meetings.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
   33 | }
      | ^
meetings.cpp: In function 'int find(int, int, int)':
meetings.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...