Submission #131158

#TimeUsernameProblemLanguageResultExecution timeMemory
131158tmwilliamlin168Meetings (IOI18_meetings)C++14
100 / 100
4999 ms303620 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; #define ll long long const int mxN=7.5e5; int n, q; pair<int, int> a[20][mxN]; vector<ll> ans; vector<int> ta[mxN], ql, qr; pair<ll, ll> st[1<<21], lz[1<<21]; pair<int, int> lca(int l, int r) { int k=31-__builtin_clz(r-l+1); return max(a[k][l], a[k][r-(1<<k)+1]); } void app(int i, pair<ll, ll> x, int l2, int r2) { if(x.first) { st[i]=make_pair(l2*x.first, r2*x.first); lz[i]=make_pair(x.first, 0); } st[i].first+=x.second; st[i].second+=x.second; lz[i].second+=x.second; } void psh(int i, int l2, int m2, int r2) { app(2*i, lz[i], l2, m2); app(2*i+1, lz[i], m2+1, r2); lz[i]=make_pair(0, 0); } void upd(int l1, int r1, pair<ll, ll> x, bool f, int i=1, int l2=0, int r2=n-1) { if(l1<=l2&&r2<=r1) { if(f||r2*x.first+x.second<st[i].second) { app(i, x, l2, r2); return; } else if(l2*x.first+x.second>=st[i].first) return; } int m2=(l2+r2)/2; psh(i, l2, m2, r2); if(l1<=m2) upd(l1, r1, x, f, 2*i, l2, m2); if(m2<r1) upd(l1, r1, x, f, 2*i+1, m2+1, r2); st[i]=make_pair(st[2*i].first, st[2*i+1].second); } ll qry(int l1, int i=1, int l2=0, int r2=n-1) { if(l2==r2) return st[i].first; int m2=(l2+r2)/2; psh(i, l2, m2, r2); return l1<=m2?qry(l1, 2*i, l2, m2):qry(l1, 2*i+1, m2+1, r2); } int dfs(int l=0, int r=n-1) { if(l>r) return -1; int u=abs(lca(l, r).second), lc=dfs(l, u-1), rc=dfs(u+1, r); upd(u, u, make_pair(1, -u), 1); for(int i : ta[u]) ans[i]=min(qry(qr[i])+(u-ql[i]+1ll)*a[0][u].first, ans[i]); upd(u, r, make_pair(0, (u-l+1ll)*a[0][u].first), 1); upd(u, r, make_pair(a[0][u].first, (~lc?qry(u-1):0)-(u-1ll)*a[0][u].first), 0); return u; } vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) { n=h.size(), q=l.size(); for(int i=0; i<n; ++i) a[0][i]=make_pair(h[i], i); for(int k=1; k<20; ++k) for(int i=0; i<=n-(1<<k); ++i) a[k][i]=max(a[k-1][i], a[k-1][i+(1<<k-1)]); ql=l, qr=r; ans=vector<ll>(q, 1e18); for(int i=0; i<q; ++i) { int w=lca(l[i], r[i]).second; ta[w].push_back(i); } dfs(); reverse(ta, ta+n); for(int i=0; i<q; ++i) tie(ql[i], qr[i])=make_pair(n-1-qr[i], n-1-ql[i]); for(int i=0; i<n; ++i) a[0][i]=make_pair(h[n-1-i], -i); for(int k=1; k<20; ++k) for(int i=0; i<=n-(1<<k); ++i) a[k][i]=max(a[k-1][i], a[k-1][i+(1<<k-1)]); dfs(); return ans; }

Compilation message (stderr)

meetings.cpp: In function 'int dfs(int, int)':
meetings.cpp:63:47: warning: unused variable 'rc' [-Wunused-variable]
  int u=abs(lca(l, r).second), lc=dfs(l, u-1), rc=dfs(u+1, r);
                                               ^~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:78:41: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    a[k][i]=max(a[k-1][i], a[k-1][i+(1<<k-1)]);
                                        ~^~
meetings.cpp:93:41: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    a[k][i]=max(a[k-1][i], a[k-1][i+(1<<k-1)]);
                                        ~^~
#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...