| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1099675 | azberjibiou | 모임들 (IOI18_meetings) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "meetings.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=750005;
const int mxM=2200005;
const int mxK=61;
const int MOD=1e9+7;
const ll INF=1e18;
int N, Q;
ll H[mxN];
pii qry[mxN];
ll l[mxN], r[mxN];
ll ldp[mxN], rdp[mxN]; // ldp[i] : [l[i]+1, i]에서 시작점을 선택해서 [l[i]+1, i-1]에 대한 최소 비용
ll rval[mxN], lval[mxN];
int ldep[mxN], rdep[mxN];
int dl[mxN], dr[mxN], mh[mxN];
pii lrng[mxN], rrng[mxN];
pll rline[mxN], lline[mxN];
ll ans[mxN];
void init(vector <int> h, vector <int> L, vector <int> R){
N=h.size();
for(int i=0;i<N;i++) H[i]=h[i];
Q=L.size();
for(int i=0;i<Q;i++) qry[i]=pii(L[i], R[i]);
}
void input(){
cin >> N >> Q;
for(int i=0;i<N;i++) cin >> H[i];
for(int i=0;i<Q;i++) cin >> qry[i].fi >> qry[i].se;
}
void make_cartesian_tree(){ // 두 산의 높이가 같으면 오른쪽에 있는 산의 높이가 더 높다
stack <int> stk;
for(int i=0;i<N;i++){
while(stk.size() && H[stk.top()]<=H[i]) stk.pop();
if(stk.size()) l[i]=stk.top();
else l[i]=-1;
stk.push(i);
}
while(stk.size()) stk.pop();
for(int i=N-1;i>=0;i--){
while(stk.size() && H[stk.top()]<H[i]) stk.pop();
if(stk.size()) r[i]=stk.top();
else r[i]=-1;
stk.push(i);
}
//dep
for(int i=0;i<N;i++){
if(l[i]==-1) ldep[i]=1;
else ldep[i]=ldep[l[i]]+1;
}
for(int i=N-1;i>=0;i--){
if(r[i]==-1) rdep[i]=1;
else rdep[i]=rdep[r[i]]+1;
}
//rng
for(int i=0;i<N;i++){
if(l[i]==-1) rrng[i]=pii(0, i);
else rrng[i]=pii(l[i]+1, i);
if(r[i]==-1) lrng[i]=pii(i, N-1);
else lrng[i]=pii(i, r[i]-1);
}
}
void make_dp(){
//길이 2짜리 segment의 비용은 0이다
vector <pii> v;
for(int i=0;i<N;i++){
if(l[i]!=-1 && r[i]!=-1) v.emplace_back(max(i-l[i], r[i]-i), i);
}
sort(all(v));
for(auto [d, i] : v){
if(H[l[i]]<=H[r[i]]){
int now=l[i];
rdp[now]=min(rdp[i]+(i-l[i])*H[i], ldp[i]+(r[i]-i)*H[i]);
}
else{
int now=r[i];
ldp[now]=min(rdp[i]+(i-l[i])*H[i], ldp[i]+(r[i]-i)*H[i]);
}
}
}
void make_lrval(){
for(int i=N-1;i>=0;i--){
if(r[i]==-1) rval[i]=(N-i)*H[i];
else rval[i]=(r[i]-i)*H[i]+rval[r[i]];
}
for(int i=0;i<N;i++){
if(l[i]==-1) lval[i]=(i+1)*H[i];
else lval[i]=(i-l[i])*H[i]+lval[l[i]];
}
}
void make_sps(){
vector <vector <int>> spsl(N, vector<int>(20)), spsr(N, vector<int>(20));
for(int j=0;j<N;j++){
spsl[j][0]=l[j];
spsr[j][0]=r[j];
}
for(int i=1;i<20;i++){
for(int j=0;j<N;j++){
if(spsl[j][i-1]==-1 || spsl[spsl[j][i-1]][i-1]==-1) spsl[j][i]=-1;
else spsl[j][i]=spsl[spsl[j][i-1]][i-1];
if(spsr[j][i-1]==-1 || spsr[spsr[j][i-1]][i-1]==-1) spsr[j][i]=-1;
else spsr[j][i]=spsr[spsr[j][i-1]][i-1];
}
}
for(int i=0;i<Q;i++){
auto [s, e]=qry[i];
int now=s;
for(int j=19;j>=0;j--){
if(spsr[now][j]!=-1 && spsr[now][j]<=e) dr[i]+=(1<<j), now=spsr[now][j];
}
now=e;
for(int j=19;j>=0;j--){
if(spsl[now][j]!=-1 && spsl[now][j]>=s) dl[i]+=(1<<j), now=spsl[now][j];
}
mh[i]=now;
}
spsl.clear(); spsr.clear();
spsl.shrink_to_fit(); spsr.shrink_to_fit();
}
void make_line(){
//rdp[now]+(now-s+1)*H[now]+rval[r[now]]-rval[hmax]+(e-hmax+1)*H[hmax] : y = -H[now]*x + rdp[now]+(now+1)*H[now]+rval[r[now]]에 -rval[hmax]+(e-hmax+1)*H[hmax]를 더한다
//ldp[now]+(e-now+1)*H[now]+lval[l[now]]-lval[hmax]+(hmax-s+1)*H[hmax] : y = H[now]*x + ldp[now]+(-now+1)*H[now]+lval[l[now]]에 -lval[hmax]+(hmax-s+1)*H[hmax]를 더한다
for(int i=0;i<N;i++){
if(l[i]!=-1) lline[i]=pll(H[i], ldp[i]+(-i+1)*H[i]+lval[l[i]]);
else lline[i]=pll();
if(r[i]!=-1) rline[i]=pll(-H[i], rdp[i]+(i+1)*H[i]+rval[r[i]]);
else rline[i]=pll();
}
}
int push_idx[mxN][21];
int lseg_idx[mxN][21][2], rseg_idx[mxN][21][2];
vector <int> dep_ct[21];
pii sgrng[4*mxN];
void make_push_idx(int idx, int s, int e, int d, int x){
push_idx[x][d]=idx;
if(s==e) return;
int mid=(s+e)/2;
if(x<=mid) make_push_idx(2*idx, s, mid, d+1, x);
else make_push_idx(2*idx+1, mid+1, e, d+1, x);
}
void make_query_idx(int idx, int s1, int e1, int s2, int e2, int d, int x, char lr){
if(s2>e1 || s1>e2) return;
if(s2<=s1 && e1<=e2){
if(lr=='r'){
if(rseg_idx[x][d][0]==0) rseg_idx[x][d][0]=idx;
else rseg_idx[x][d][1]=idx;
}
else{
if(lseg_idx[x][d][0]==0) lseg_idx[x][d][0]=idx;
else lseg_idx[x][d][1]=idx;
}
return;
}
int mid=(s1+e1)/2;
make_query_idx(2*idx, s1, mid, s2, e2, d+1, x, lr);
make_query_idx(2*idx+1, mid+1, e1, s2, e2, d+1, x, lr);
}
void make_seg_idx(int idx, int s, int e, int d){
dep_ct[d].push_back(idx);
sgrng[idx]=pii(s, e);
if(s==e) return;
int mid=(s+e)/2;
make_seg_idx(2*idx, s, mid, d+1);
make_seg_idx(2*idx+1, mid+1, e, d+1);
}
void make_idx(){
for(int i=1;i<=N;i++){
make_push_idx(1, 1, N, 0, i);
}
for(int i=0;i<Q;i++){
if(dl[i]>=1) make_query_idx(1, 1, N, ldep[qry[i].se]-dl[i]+1, ldep[qry[i].se], 0, i, 'l');
if(dr[i]>=1) make_query_idx(1, 1, N, rdep[qry[i].fi]-dr[i]+1, rdep[qry[i].fi], 0, i, 'r');
}
make_seg_idx(1, 1, N, 0);
/*
for(int i=1;i<=N;i++) for(int j=0;j<3;j++) printf("push_idx[%d][%d]=%d\n", i, j, push_idx[i][j]);
for(int i=0;i<Q;i++){
for(int j=0;j<5;j++){
printf("lseg_idx[%d][%d]=%d %d\n", i, j, lseg_idx[i][j][0], lseg_idx[i][j][1]);
}
}
for(int i=0;i<5;i++){
printf("i=%d: ", i);
for(int x : dep_ct[i]) printf("%d ", x);
}
*/
}
struct Node{
int val;
int llink, rlink;
Node() : val(), llink(), rlink() {}
Node(int val, int llink, int rlink) : val(val), llink(llink), rlink(rlink) {}
};
struct event{
int idx;
int e1, e2;
event() : idx(), e1(), e2() {}
event(int idx, int e1, int e2) : idx(idx), e1(e1), e2(e2) {}
};
char swp_typ;
vector <Node> seg[4*mxN];
vector <event> swp[mxN], imswp; // imswp means immediate swap, where intersection <= x
int now_x;
void seg_init(int current_depth){
for(int x : dep_ct[current_depth]){
auto [s, e]=sgrng[x];
seg[x].resize(e-s+3);
seg[x][0].rlink=e-s+2;
seg[x][e-s+2].llink=0;
for(int i=1;i<=e-s+1;i++) seg[x][i].rlink=seg[x][i].llink=-1;
}
}
ll intersection(int e1, int e2){
//printf("swp_typ=%c\n", swp_typ);
//printf("e1=%d, e2=%d\n", e1, e2);
pll c1, c2;
if(swp_typ=='r') c1=rline[e1], c2=rline[e2];
else c1=lline[e1], c2=lline[e2];
if(swp_typ=='r') assert(c1.fi<=c2.fi);
else assert(c1.fi>=c2.fi);
if(c1.fi==c2.fi){
if(c1.se<=c2.se) return (swp_typ=='r' ? 0 : N);
else return (swp_typ=='r' ? N+1 : -1);
}
if(swp_typ=='r'){
pll c3=pll(c1.fi-c2.fi, c1.se-c2.se);
if(c3.se<=0) return -1;
return (c3.se%(-c3.fi)==0 ? c3.se/(-c3.fi) : c3.se/(-c3.fi)+1);
}
else{
pll c3=pll(c2.fi-c1.fi, c2.se-c1.se);
if(c3.se<=0) return -1;
return (c3.se%(-c3.fi)==0 ? c3.se/(-c3.fi) : c3.se/(-c3.fi));
}
} // e1이 e2보다 작아지는 순간을 리턴
void add_swp(int idx, int ln, int rn){
int lv=seg[idx][ln].val, rv=seg[idx][rn].val;
ll itx=intersection(lv, rv);
if(swp_typ=='r'){
if(itx<=now_x) imswp.emplace_back(idx, lv, rv);
else if(itx<=N-1) swp[itx].emplace_back(idx, lv, rv);
}
else{
if(itx>=now_x) imswp.emplace_back(idx, lv, rv);
else if(itx>=0) swp[itx].emplace_back(idx, lv, rv);
}
}
void add_node(int idx, int ln, int now, int rn, int x){
//printf("add: ");
//printf("idx=%d, ln, now, rn, x=%d %d %d %d\n", idx, ln, now, rn, x);
seg[idx][now].rlink=rn;
seg[idx][now].llink=ln;
seg[idx][ln].rlink=now;
seg[idx][rn].llink=now;
seg[idx][now].val=x;
if(ln!=0) add_swp(idx, ln, now);
if(rn!=seg[idx].size()-1) add_swp(idx, now, rn);
}
void del_node(int idx, int now){
//printf("del: idx, now = %d %d\n", idx, now);
int ln=seg[idx][now].llink, rn=seg[idx][now].rlink;
seg[idx][ln].rlink=rn;
seg[idx][rn].llink=ln;
seg[idx][now].llink=seg[idx][now].rlink=seg[idx][now].val=-1;
if(ln!=0 && rn!=seg[idx].size()-1) add_swp(idx, ln, rn);
}
void add(int idx, int pos, int x){
int rn=seg[idx].size()-1, ln=seg[idx][rn].llink, s=sgrng[idx].fi;
add_node(idx, ln, pos-s+1, rn, x);
}
void swap_f(event t){
auto [idx, e1, e2]=t;
int s=sgrng[idx].fi;
int idx1=(swp_typ=='r' ? rdep[e1] : ldep[e1])-s+1, idx2=(swp_typ=='r' ? rdep[e2] : ldep[e2])-s+1;
if(seg[idx][idx1].rlink==idx2 && seg[idx][idx2].llink==idx1 && seg[idx][idx1].val==e1 && seg[idx][idx2].val==e2){
del_node(idx, idx2);
}
}
ll seg_solv(int idx, ll x){
int bk=seg[idx].back().llink;
if(bk==0) return INF;
pll ln=(swp_typ=='r' ? rline[seg[idx][bk].val] : lline[seg[idx][bk].val]);
return ln.fi*x+ln.se;
}
void del(int idx, int x){
int bk=seg[idx].back().llink;
if(bk!=0 && seg[idx][bk].val==x){
del_node(idx, bk);
}
}
vector <int> ppct[mxN]; // i번 직선을 push하면 i, pop하면 -i-1
vector <int> qct[mxN];
void init_sweep(){
for(int i=0;i<4*mxN;i++) if(seg[i].size()) seg[i].clear(), seg[i].shrink_to_fit();
for(int i=0;i<mxN;i++) if(swp[i].size()) swp[i].clear(), swp[i].shrink_to_fit();
imswp.clear(), imswp.shrink_to_fit();
now_x=0;
for(int i=0;i<mxN;i++) if(ppct[i].size()) ppct[i].clear(), ppct[i].shrink_to_fit();
for(int i=0;i<mxN;i++) if(qct[i].size()) qct[i].clear(), qct[i].shrink_to_fit();
}
void solv_query(){
for(int i=0;i<Q;i++) ans[i]=INF;
//가장 높은 곳에서 시작
for(int i=0;i<Q;i++) ans[i]=min(ans[i], (qry[i].se-qry[i].fi+1)*H[mh[i]]);
swp_typ='r';
for(int z=0;z<21;z++){
seg_init(z);
//dpr에 대해서 segment tree sweeping
for(int i=N-1;i>=0;i--){ // 깊이가 낮은 것부터 push -> i--
if(r[i]==-1) continue;
ppct[rrng[i].fi].push_back(i);
}
// i에 대해서 push -> 쿼리 시행 -> i가 끝나면 i를 pop
for(int i=0;i<Q;i++) qct[qry[i].fi].push_back(i);
for(int i=0;i<N;i++){
now_x=i;
//add element
for(int x : ppct[i]){ // add element
if(push_idx[rdep[x]][z]!=0) add(push_idx[rdep[x]][z], rdep[x], x);
}
//maintain list
while(swp[i].size() || imswp.size()){
if(swp[i].size()){
event t=swp[i].back();
swp[i].pop_back();
swap_f(t);
}
else{
event t=imswp.back();
imswp.pop_back();
swap_f(t);
}
}
//solve queries
for(int x : qct[i]){
int e=qry[x].se;
int hmax=mh[x];
for(int k=0;k<=1;k++) if(rseg_idx[x][z][k]!=0) ans[x]=min(ans[x], seg_solv(rseg_idx[x][z][k], i)-rval[hmax]+(e-hmax+1)*H[hmax]);
}
//pop
if(push_idx[rdep[i]][z]!=0) del(push_idx[rdep[i]][z], i);
}
init_sweep();
}
swp_typ='l';
for(int z=0;z<21;z++){
seg_init(z);
//dpl에 대해서 segment tree sweeping
for(int i=0;i<N;i++){ // 깊이가 낮은 것부터 push -> i++
if(l[i]==-1) continue;
ppct[lrng[i].se].push_back(i);
}
// i에 대해서 push -> 쿼리 시행 -> i가 끝나면 i를 pop
for(int i=0;i<Q;i++) qct[qry[i].se].push_back(i);
for(int i=N-1;i>=0;i--){
now_x=i;
//add element
for(int x : ppct[i]){ // add element
if(push_idx[ldep[x]][z]!=0) add(push_idx[ldep[x]][z], ldep[x], x);
}
//maintain list
while(swp[i].size() || imswp.size()){
if(swp[i].size()){
event t=swp[i].back();
swp[i].pop_back();
swap_f(t);
}
else{
event t=imswp.back();
imswp.pop_back();
swap_f(t);
}
}
//solve queries
for(int x : qct[i]){
int s=qry[x].fi;
int hmax=mh[x];
for(int k=0;k<=1;k++) if(lseg_idx[x][z][k]!=0) ans[x]=min(ans[x], seg_solv(lseg_idx[x][z][k], i)-lval[hmax]+(hmax-s+1)*H[hmax]);
}
//pop
if(push_idx[ldep[i]][z]!=0) del(push_idx[ldep[i]][z], i);
}
init_sweep();
}
for(int i=0;i<Q;i++) cout << ans[i] << '\n';
}
void solv(){
make_cartesian_tree();
make_dp();
make_lrval();
make_sps();
make_line();
make_idx();
solv_query();
}
vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R) {
init(h, L, R);
solv();
vector <ll> C(Q);
for(int j=0;j<Q;j++) C[j]=ans[j];
return C;
}
int main()
{
gibon
input();
solv();
}