| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1054872 | Ahmed57 | 모임들 (IOI18_meetings) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#define int long long
int arr[100001];
int logg[100001];
int table[100001][17];
int n ,q;
map<int,vector<int>> val;
map<pair<int,int>,int> mp;
int solve(int l,int r){
if(l>r)return 0;
if(dp.find(make_pair(l,r))!=dp.end())return dp[{l,r}];
int sz = (r-l+1);
int ind = max(table[l][logg[sz]],table[r-(1<<logg[sz])+1][logg[sz]]);
int it = lower_bound(val[ind].begin(),val[ind].end(),l)-val[ind].begin();
int it2 = it;
while(it2<val[ind].size()&&val[ind][it2]<=r)it2++;
it2--;
int ma = 1e18;
{//l
ma = min(ma,solve(l,val[ind][it]-1)+((r-l+1)-(val[ind][it]-l))*ind);
}
{//r
ma = min(ma,solve(val[ind][it2]+1,r)+((r-l+1)-(r-val[ind][it2]))*ind);
}
for(int i = it;i<it2;i++){
ma = min(ma,solve(val[ind][i]+1,val[ind][i+1]-1)+((r-l+1)-(val[ind][i+1]-val[ind][i]-1))*ind);
}
return dp[{l,r}] = ma;
}
vector<long long> minimum_costs(vector<int32_t> H, vector<int32_t> L, vector<int32_t> R){
n = H.size();
q = L.size();
for(int i = 0;i<n;i++){
table[i][0] = H[i];
arr[i] = H[i];
val[arr[i]].push_back(i);
}
for(int j = 1;j<17;j++){
for(int i = 0;i<n-(1<<j)+1;i++){
table[i][j] = max(table[i][j-1],table[i+(1<<(j-1))][j-1]);
}
}
logg[1] = 0;
for(int i = 2;i<=n;i++)logg[i] = logg[i/2]+1;
vector<long long> an;
for(int i = 0;i<q;i++){
an.push_back(solve(L[i],R[i]));
}
return an;
}