제출 #995500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995500		hirayuu_oj	모임들 (IOI18_meetings)	C++17	36 / 100	640 ms	6492 KiB

meetings

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
ll LINF=(1LL<<61)-1;
ll MINF=1LL<<40;
int INF=INT_MAX>>1;

template<class S>
void out_vector(vector<S> v){
    for(S i:v)cerr<<i<<" ";
    cerr<<"\n";
}
#include "meetings.h"

struct SegmentTree{
    
    using T=array<int,4>;
    T op(T x,T y){
        T ret;
        ret[0]=max({x[0],y[0],x[2]+y[1]});
        ret[1]=x[1];
        if(x[1]==x[3])ret[1]+=y[1];
        ret[2]=y[2];
        if(y[2]==y[3])ret[2]+=x[2];
        ret[3]=x[3]+y[3];
        return ret;
    }
    T e(){
        return {0,0,0,0};
    }

    vector<T> val;
    int size;
    SegmentTree(int sz){
        size=sz;
        val.resize(sz*2,e());
    }
    void set(int pos,T v){
        pos+=size;
        val[pos]=v;
        while(pos>1){
            pos>>=1;
            val[pos]=op(val[pos*2],val[pos*2+1]);
        }
    }
    T get(int lf,int ri){
        lf+=size;
        ri+=size;
        T rel=e();
        T rer=e();
        while(lf<ri){
            if(lf&1){
                rel=op(rel,val[lf]);
                lf++;
            }
            if(ri&1){
                ri--;
                rer=op(val[ri],rer);
            }
            lf/=2;
            ri/=2;
        }
        return op(rel,rer);
    }
};
//max,lf,ri,sz
using T=array<int,4>;
T op(T x,T y){
    T ret;
    ret[0]=max({x[0],y[0],x[2]+y[1]});
    ret[1]=x[1];
    if(x[1]==x[3])ret[1]+=y[1];
    ret[2]=y[2];
    if(y[2]==y[3])ret[2]+=x[2];
    ret[3]=x[3]+y[3];
    return ret;
}
T e(){
    return {0,0,0,0};
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    int Q = L.size();
    int N=H.size();
    if(N>5000||Q>5000){
        SegmentTree seg(N);
        vector<ll> C(Q);
        rep(i,N){
            if(H[i]==1){
                seg.set(i,{1,1,1,1});
            }
            else{
                seg.set(i,{0,0,0,1});
            }
        }
        rep(i,Q){
            C[i]=(R[i]+1-L[i])*2-seg.get(L[i],R[i]+1)[0];
        }
        return C;
    }
    vector<ll> C(Q);
    rep(i,Q){
        vector<ll> cnt(N);
        stack<array<ll,3>> st;
        st.push({L[i]-1,LINF,0});
        ll cst=0;
        rep2(j,L[i],R[i]+1){
            while(st.top()[1]<H[j]){
                cst-=st.top()[2];
                st.pop();
            }
            cst+=(j-st.top()[0])*H[j];
            st.push({j,H[j],(j-st.top()[0])*H[j]});
            cnt[j]+=cst;
        }
        while(!st.empty())st.pop();
        st.push({R[i]+1,LINF,0});
        cst=0;
        for(int j=R[i]; j>=L[i]; j--){
            while(st.top()[1]<H[j]){
                cst-=st.top()[2];
                st.pop();
            }
            cst+=(st.top()[0]-j)*H[j];
            st.push({j,H[j],(st.top()[0]-j)*H[j]});
            cnt[j]+=cst;
        }
        C[i]=LINF;
        rep2(j,L[i],R[i]+1){
            C[i]=min(C[i],cnt[j]-H[j]);
        }
    }
    return C;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40