oj.uz

Submission #760457

# Submission time Handle Problem Language Result Execution time Memory
760457 2023-06-17T15:45:12 Z alexander707070 Meetings (IOI18_meetings) C++14
41 / 100
 3631 ms 634740 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 129 ms 48028 KB Output is correct
3 Correct 3092 ms 632616 KB Output is correct
4 Correct 3034 ms 632644 KB Output is correct
5 Correct 2997 ms 632648 KB Output is correct
6 Correct 3310 ms 632644 KB Output is correct
7 Correct 3018 ms 632640 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 129 ms 48028 KB Output is correct
3 Correct 3092 ms 632616 KB Output is correct
4 Correct 3034 ms 632644 KB Output is correct
5 Correct 2997 ms 632648 KB Output is correct
6 Correct 3310 ms 632644 KB Output is correct
7 Correct 3018 ms 632640 KB Output is correct
8 Correct 3509 ms 632828 KB Output is correct
9 Correct 2963 ms 634652 KB Output is correct
10 Correct 3090 ms 634740 KB Output is correct
11 Correct 3199 ms 634636 KB Output is correct
12 Correct 2919 ms 634644 KB Output is correct
13 Correct 3101 ms 634648 KB Output is correct
14 Correct 2804 ms 634720 KB Output is correct
15 Correct 3631 ms 634648 KB Output is correct
16 Correct 3122 ms 634676 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -