Submission #137842

#TimeUsernameProblemLanguageResultExecution timeMemory
137842bensonlzlMeetings (IOI18_meetings)C++14
0 / 100
3 ms504 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pi; typedef pair<int,pi> pii; ll N, Q; ll mount[1000005]; struct node{ node *left = nullptr, *right = nullptr; int S, E, pre1 = 0, suff1 = 0, seg1 = 0; node(int _s, int _e){ S = _s; E = _e; if (S == E){ pre1 = suff1 = seg1 = (mount[S] == 1); return; } left = new node(S,(S+E)/2); right = new node((S+E)/2+1,E); if (left->pre1 == left->E - left->S + 1){ pre1 = left->pre1 + right->pre1; } else pre1 = left->pre1; if (right->suff1 == right->E - right->S + 1){ suff1 = right->suff1 + right->suff1; } else suff1 = right->suff1; seg1 = max(left->seg1,right->seg1); seg1 = max(seg1,left->suff1 + right->pre1); } pii query(int l, int r){ if (l > E || r < S || r < l) return pii(0,pi(0,0)); if (l <= S && E <= r) return pii(seg1,pi(pre1,suff1)); pii l1 = left->query(l,min(r,(S+E)/2)), r1 = right->query(max((S+E)/2+1,l),r); int sg = max(max(l1.first,r1.first),l1.second.second+r1.second.first); int pr, su; if (l1.second.first == max(0,left->E-l+1)){ pr = l1.second.first + r1.second.first; } else pr = l1.second.first; if (r1.second.second == max(0,r-right->S+1)){ su = r1.second.second + l1.second.second; } else su = r1.second.second; return pii(sg,pi(pr,su)); } } *root; vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) { vector<ll> ans; N = H.size(); Q = L.size(); for (int i = 0; i < N; ++i){ mount[i] = H[i]; } if (N <= 5000){ for (int i = 0; i < Q; ++i){ ll maxi = 0; vector<ll> pos; pos.resize(R[i]-L[i]+1,0); for (ll j = L[i]; j <= R[i]; ++j){ maxi = max(maxi,mount[j]); pos[j-L[i]] += (j-L[i]+1)*maxi; } maxi = 0; for (ll j = R[i]; j >= L[i]; --j){ maxi = max(maxi,mount[j]); pos[j-L[i]] += (R[i]-j+1)*maxi; } ll mini = 1e17; for (int j = 0; j < R[i]-L[i]+1; ++j){ mini = min(mini,pos[j]); } ans[i] = mini; } } else{ root = new node(0,N-1); for (int i = 0; i < Q; ++i){ ans.push_back(2*(R[i]-L[i]+1)-root->query(L[i],R[i]).first); } return ans; } }

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:90:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#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...