| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 760448 | alexander707070 | 통행료 (IOI18_highway) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define MAXN 100007
#define MAXH 3
using namespace std;
struct event{
int pos;
int val;
int from;
int type;
inline friend bool operator < (event fr,event sc){
return fr.pos<sc.pos;
}
};
const int inf=1e9+7;
int n,h[MAXN],q,l,r,pt,pr[MAXN],nxt[MAXN],lt,rt,lpos,rpos;
long long curr;
vector< pair<int,int> > st;
vector<long long> ans;
vector<event> w;
long long calc[MAXN][MAXH+1][MAXH+1];
void precalc(){
st.clear(); st.push_back({inf,0});
for(int i=1;i<=n;i++){
while(h[i]>=st.back().first){
st.pop_back();
}
pr[i]=st.back().second;
st.push_back({h[i],i});
pt=st.size()-1; curr=0;
for(int f=h[i];f<=MAXH;f++){
while(st[pt].first<=f){
curr+=(long long) st[pt].first*(st[pt].second-st[pt-1].second);
pt--;
}
for(int k=1;k<=MAXH;k++){
calc[i][f][k]+=curr;
}
}
}
st.clear(); st.push_back({inf,n+1});
for(int i=n;i>=1;i--){
while(h[i]>=st.back().first){
st.pop_back();
}
nxt[i]=st.back().second;
st.push_back({h[i],i});
pt=st.size()-1; curr=0;
for(int f=h[i];f<=MAXH;f++){
while(st[pt].first<=f){
curr+=(long long) st[pt].first*(st[pt-1].second-st[pt].second);
pt--;
}
for(int k=1;k<=MAXH;k++){
calc[i][k][f]+=(long long) curr-h[i];
}
}
}
}
int tree[4*MAXN][MAXH+1][MAXH+1];
int best(int x,int y,int lt,int rt){
if(calc[x][lt][rt]<calc[y][lt][rt])return x;
return y;
}
void build(int v,int l,int r,int lt,int rt){
if(l==r){
tree[v][lt][rt]=l;
}else{
int tt=(l+r)/2;
build(2*v,l,tt,lt,rt);
build(2*v+1,tt+1,r,lt,rt);
tree[v][lt][rt]=best(tree[2*v][lt][rt],tree[2*v+1][lt][rt],lt,rt);
}
}
int getmin(int v,int l,int r,int ll,int rr,int lt,int rt){
if(ll>rr)return 0;
if(l==ll and r==rr){
return tree[v][lt][rt];
}else{
int tt=(l+r)/2;
return best( getmin(2*v,l,tt,ll,min(tt,rr),lt,rt) , getmin(2*v+1,tt+1,r,max(tt+1,ll),rr,lt,rt) ,lt,rt );
}
}
vector<long long> minimum_costs(vector<int> H,vector<int> L,vector<int> R){
n=int(H.size()); q=int(L.size());
for(int i=1;i<=n;i++){
h[i]=H[i-1];
}
precalc();
for(int i=1;i<=MAXH;i++){
for(int f=1;f<MAXH;f++){
calc[0][i][f]=1e16;
build(1,1,n,i,f);
}
}
for(int i=0;i<q;i++){
l=L[i]+1; r=R[i]+1;
w.clear();
for(int f=l;f<=r;f=nxt[f]){
w.push_back({f,h[f],f,0});
}
for(int f=r;f>=l;f=pr[f]){
w.push_back({max(pr[f]+1,l),h[f],f,1});
}
w.push_back({r+1,0,0});
sort(w.begin(),w.end());
curr=1e16;
for(int f=0;f<w.size()-1;f++){
if(w[f].type==0){lt=w[f].val; lpos=pr[w[f].pos]+1;}
if(w[f].type==1){rt=w[f].val; rpos=nxt[w[f].from]-1;}
if(w[f].pos!=w[f+1].pos){
curr=min(curr,(long long) calc[getmin(1,1,n,w[f].pos,w[f+1].pos-1,lt,rt)][lt][rt]-(l-lpos)*lt-(rpos-r)*rt);
}
}
ans.push_back(curr);
}
return ans;
}
/*
int main(){
minimum_costs({1,1,2,2,1,1,1,1,2}, {0}, {8});
//minimum_costs({2, 4, 3, 5}, {0, 1}, {2, 3});
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
}
*/