Submission #1050851

#TimeUsernameProblemLanguageResultExecution timeMemory
1050851parsadox2Meetings (IOI18_meetings)C++17
0 / 100
20 ms21608 KiB
#include <bits/stdc++.h> #include "meetings.h" using namespace std; const int N = 75e4 + 10 , Lg = 20; const long long inf = 1e17; int n , q , nexR[N] , nexL[N]; long long ansR[N] , ansL[N]; vector <int> a , L , R; struct item{ long long ans , sum; int l , r; }; item valL[N][Lg] , valR[N][Lg]; item MergeL(item al , item ar) { item res; res.l = al.l; res.r = ar.r; if(res.l == -1 || res.r == -1) { res.sum = res.ans = inf; return res; } res.sum = al.sum + ar.sum; res.ans = min(al.ans + 1LL * (ar.r - ar.l) * a[ar.l] , ar.ans + al.sum); return res; } item MergeR(item al , item ar) { item res; res.l = al.l; res.r = ar.r; if(res.l == -1 || res.r == -1) { res.sum = res.ans = inf; return res; } res.sum = al.sum + ar.sum; res.ans = min(al.ans + ar.sum , ar.ans + 1LL * (al.r - al.l) * a[al.r]); return res; } vector <long long> minimum_costs(vector <int> H , vector <int> LL , vector <int> RR) { vector <long long> res; a = H; L = LL; R = RR; n = H.size(); q = L.size(); vector <int> st; for(int i = 0 ; i < n ; i++) { nexL[i] = -1; nexR[i] = -1; while(!st.empty()) { if(a[st.back()] < a[i]) { nexR[st.back()] = i; st.pop_back(); } else { nexL[i] = st.back(); break; } } st.push_back(i); } for(int i = 0 ; i < n ; i++) { ansL[i] = inf; if(nexL[i] == -1) continue; if(nexL[i] == i - 1) { ansL[i] = a[i] + a[i - 1]; continue; } vector <int> pos; int las = i - 1; while(las != nexL[i]) { pos.push_back(las); las = nexL[las]; } long long tmp = 0; while(!pos.empty()) { int now = pos.back(); pos.pop_back(); ansL[i] = min(ansL[i] , tmp + ansL[now] + a[i] + 1LL * (i - now - 1) * a[now]); tmp += a[las]; tmp += 1LL * (now - las - 1) * a[now]; las = now; } } for(int i = n - 1 ; i >= 0 ; i--) { ansR[i] = inf; if(nexR[i] == -1) continue; if(nexR[i] == i + 1) { ansR[i] = a[i] + a[i + 1]; continue; } vector <int> pos; int las = i + 1; while(las != nexR[i]) { pos.push_back(las); las = nexR[las]; } long long tmp = 0; while(!pos.empty()) { int now = pos.back(); pos.pop_back(); ansR[i] = min(ansR[i] , tmp + ansR[now] + a[i] + 1LL * (now - i - 1) * a[now]); tmp += a[las]; tmp += 1LL * (las - now - 1) * a[now]; las = now; } } for(int i = 0 ; i < n ; i++) { valL[i][0].ans = ansL[i]; valL[i][0].l = nexL[i]; valL[i][0].r = i; if(nexL[i] == -1) valL[i][0].sum = inf; else valL[i][0].sum = a[nexL[i]] + 1LL * (i - nexL[i] - 1) * a[i]; valR[i][0].ans = ansR[i]; valR[i][0].r = nexR[i]; valR[i][0].l = i; if(nexR[i] == -1) valR[i][0].sum = inf; else valR[i][0].sum = a[nexR[i]] + 1LL * (nexR[i] - i - 1) * a[i]; } for(int j = 1 ; j < Lg ; j++) for(int i = 0 ; i < n ; i++) { if(valL[i][j - 1].l == -1) valL[i][j] = valL[i][j - 1]; else valL[i][j] = MergeL(valL[valL[i][j - 1].l][j - 1] , valL[i][j - 1]); if(valR[i][j - 1].r == -1) valR[i][j] = valR[i][j - 1]; else valR[i][j] = MergeR(valR[i][j - 1] , valR[valR[i][j- 1].r][j - 1]); } for(int asd = 0 ; asd < q ; asd++) { long long ans = inf; if(L[asd] == R[asd]) { ans = a[L[asd]]; res.push_back(ans); continue; } bool flg = false; int pos = L[asd]; item now; for(int i = Lg - 1 ; i >= 0 ; i--) if(valR[pos][i].r <= R[asd] && valR[pos][i].r != -1) { if(!flg) now = valR[pos][i]; else now = MergeR(now , valR[pos][i]); flg = true; pos = now.r; } if(flg) ans = min(ans , now.ans + 1LL * (R[asd] - now.r) * a[now.r]); flg = false; pos = R[asd]; for(int i = Lg - 1 ; i >= 0 ; i--) if(valL[pos][i].l >= L[asd] && valL[pos][i].l != -1) { if(!flg) now = valL[pos][i]; else now = MergeL(valL[pos][i] , now); flg = true; pos = now.l; } if(flg) ans = min(ans , now.ans + 1LL * (now.l - L[asd]) * a[now.l]); 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...