(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #1024121

#TimeUsernameProblemLanguageResultExecution timeMemory
1024121kymMeetings (IOI18_meetings)C++14
0 / 100
59 ms4012 KiB
#include "meetings.h" #include <bits/stdc++.h> #define int long long using namespace std; vector<int> vs[25]; const int maxn=750005; typedef pair<int,int>pi; map<pi,int>mp; const int oo = 1'000'000'000'000'000'000ll; vector<long long> minimum_costs(vector<int32_t> H, vector<int32_t> L, vector<int32_t> R) { int n=H.size(); for(int i=0;i<n;i++){ vs[H[i]].push_back(i); } for(int i=0;i<n;i++){ //cerr<<i<<":\n"; vector<pi>vidx; for(int k=1;k<=20;k++){ auto it=upper_bound(vs[k].begin(),vs[k].end(),i); if(it!=vs[k].begin()){ vidx.push_back({*prev(it),k}); // {index, value from this point onwards} } } sort(vidx.begin(),vidx.end(),greater<pi>()); int cur=H[i]; int sum=0; int lst=i;//covered including this idx vector<pi> ls,rs; ls.push_back({i,0}); rs.push_back({i,0}); for(auto x:vidx){ if(x.second>cur){ sum += (lst-x.first-1)*cur + x.second; cur=x.second; lst=x.first; ls.push_back({x.first,sum}); } } vidx.clear(); for(int k=1;k<=20;k++){ auto it=lower_bound(vs[k].begin(),vs[k].end(),i); if(it!=vs[k].end()){ vidx.push_back({*it,k}); } } sort(vidx.begin(),vidx.end()); cur=H[i]; sum=0; lst=i; for(auto x:vidx){ if(x.second>cur){ sum += (x.first-lst-1)*cur + x.second; cur=x.second; lst=x.first; rs.push_back({x.first,sum}); } } for(auto x:ls){ for(auto y:rs){ int lf=x.first; int rg=y.first; if(lf>rg)continue; int su=x.second+y.second+H[i]; if(mp.find({lf,rg}) == mp.end() || mp[{lf,rg}]>su){ //cerr<<lf<<","<<rg<<":"<<su<<endl; mp[{lf,rg}]=su; } } } } int Q=L.size(); vector<int> res; for(int i=0;i<Q;i++){ int S=L[i],E=R[i]; vector<pi>lf,rg; for(int k=1;k<=20;k++){ auto it=lower_bound(vs[k].begin(),vs[k].end(),S); if(it!=vs[k].end() && *it <= E){ lf.push_back({*it,k}); } } for(int k=1;k<=20;k++){ auto it=upper_bound(vs[k].begin(),vs[k].end(),E); if(it!=vs[k].begin() && *prev(it) >= S){ rg.push_back({*prev(it),k}); } } sort(lf.begin(),lf.end()); sort(rg.begin(),rg.end(),greater<pi>()); vector<pi>L,R; for(auto x:lf){ if(L.empty() || x.second > L.back().second){ L.push_back(x); } } for(auto x:rg){ if(R.empty() || x.second > R.back().second){ R.push_back(x); } } int ans=oo; for(auto x:L){ for(auto y:R){ if(x.first<=y.first){ //cerr<<x.first<<" "<<y.first<<endl; if(mp.find({x.first,y.first}) != mp.end()){ ans=min(ans,mp[{x.first,y.first}] + (x.first-S)*x.second+(E-y.first)*y.second); } } } } res.push_back(ans); } return res; }
#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...