Submission #760457

#	Time	Username	Problem	Language	Result	Execution time	Memory
760457		alexander707070	Meetings (IOI18_meetings)	C++14	41 / 100	3631 ms	634740 KiB

meetings

#include<bits/stdc++.h>
#define MAXN 100007
#define MAXH 21
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+1==r){
        tree[v][lt][rt]=best(l,l+1,lt,rt);
    }else 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){
        if(l==r)return l;
        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]<<" ";
     }
}
*/

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:133:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for(int f=0;f<w.size()-1;f++){
      |                     ~^~~~~~~~~~~

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