Submission #944776

#	Time	Username	Problem	Language	Result	Execution time	Memory
944776		salmon	Meetings (IOI18_meetings)	C++14	60 / 100	2514 ms	298212 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;

int N;
int Q;
int lst[250100];
long long int num[200100][25];
pair<int,int> st[500100];
pair<int,int> st1[500100];


void build(int i, int s, int e){
    if(s == e){
        st[i] = {lst[s],s};
        st1[i] = {lst[s],-s};
        return;
    }

    int m = (s + e)/2;

    build(i * 2,s,m);
    build(i * 2 + 1, m + 1, e);

    st[i] = max(st[i * 2],st[i * 2 + 1]);
    st1[i] = max(st1[i * 2],st1[i * 2 + 1]);
}

pair<int,int> query(int i, int s, int e, int S, int E){
    if(S <= s && e <= E){
        return st[i];
    }

    int m = (s + e)/2;

    if(S <= m && m < E){
        return max(query(i*2,s,m,S,E), query(i*2+1,m+1,e,S,E));
    }

    if(S <= m) return query(i * 2, s, m ,S, E);
    if(m < E) return query(i * 2 + 1, m + 1, e, S, E);
}

pair<int,int> query1(int i, int s, int e, int S, int E){
    if(S <= s && e <= E){
        return st1[i];
    }

    int m = (s + e)/2;

    if(S <= m && m < E){
        return max(query1(i*2,s,m,S,E), query1(i*2+1,m+1,e,S,E));
    }

    if(S <= m) return query1(i * 2, s, m ,S, E);
    if(m < E) return query1(i * 2 + 1, m + 1, e, S, E);
}


long long int recurse(int j, int l ,int r){
    if(l > r) return 0;
    if(l == r && lst[l] == j){
        num[l][j] = 0;
        return j;
    }

    long long int small = 1e18;

    vector<int> temp = {l - 1};

    for(int i = l; i <= r; i++){
        if(lst[i] == j) temp.push_back(i);
    }

    temp.push_back(r + 1);

    for(int i = 0; i < temp.size() - 1; i++){
        long long int vum = recurse(j - 1,temp[i] + 1, temp[i + 1] - 1) + (temp[i] - l + 1 + r - temp[i + 1] + 1) * j;
        small = min(small, vum);
        num[temp[i + 1] - 1][j] = vum - (r - l + 1) * j;
    }

    return small;
}

struct node{

    int s, e, m;
    node *l, *r;
    long long int v;
    int j;

    node(int S, int E, int J){
        s = S;
        e = E;
        m = (s + e)/2;
        j = J;

        if(s == e){
            v = num[s][j];
        }
        else{
            l = new node(s,m,J);
            r = new node(m + 1, e,J);

            v = min(l -> v, r -> v);
        }
    }

    long long int query(int S, int E){
        if(S <= s && e <= E) return v;

        long long int V = 1e18;

        if(S <= m){
            V = min(V , l -> query(S,E));
        }
        if(m < E){
            V = min(V, r -> query(S,E));
        }
        return V;
    }

} *nodes[25];


vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    N = H.size();
    Q = L.size();

    if(N >= 5001){

        for(int i = 1; i <= N; i++){
            lst[i] = H[i - 1];
        }

        for(int i = 0; i <= N; i++){
            for(int j = 0; j <= 20; j++){
                num[i][j] = 1e18;
            }
        }

        recurse(20,1,N);

        for(int j = 0; j <= 20; j++){
            nodes[j] = new node(1,N,j);
        }

        /*for(int j = 0; j <= 20; j++){
            for(int i = 1 ; i <= N; i++){
                printf("%d ",num[i][j]);
            }
            printf("\n");
        }*/

        build(1,1,N);

        vector<long long int> banna;

        for(int i = 0; i < Q; i++){
            vector<vector<long long int>> v1;

            v1.push_back({0,L[i]+1,R[i]+1,0});

            long long int ans = 1e18;

            long long int cont = 20;
            while(cont >= 0){
                vector<vector<long long int>> temp;
                //printf("%d %d\n",ans,cont);
                while(!v1.empty()){
                    vector<long long int> v = v1.back();
                    v1.pop_back();

                    //printf("%d %d %d %d\n",v[0],v[1],v[2],v[3]);

                    long long int k = ans;

                    pair<int,int> p = query(1,1,N,v[1],v[2]);
                    if(p.first != cont){
                        temp.push_back(v);
                        continue;
                    }

                    if(v[2] == v[1]){
                        ans = min(ans, cont + v[0]);
                        continue;
                    }

                    pair<int,int> p1 = query1(1,1,N,v[1],v[2]);

                    ans = min(ans, p1.first * (v[2] - v[1] + 1));

                    if(v[3] == 0){
                        if(p.second == -p1.second){
                            int it = p.second;
                            if(it != v[1]){
                                temp.push_back({v[0] + cont * (v[2] - it + 1), v[1], it - 1,2});
                            }
                            if(it != v[2]){
                                temp.push_back({v[0] + cont * (it - v[1] + 1), it + 1, v[2],1});
                            }
                        }
                        else{
                            int it = -p1.second;
                            int it1 = p.second;

                            if(it != v[1]){
                                temp.push_back({v[0] + cont * (v[2] - it + 1), v[1], it - 1, 2});
                            }
                            if(it1 != v[2]){
                                temp.push_back({v[0] + cont * (it1 - v[1] + 1), it1 + 1, v[2],1});
                            }
                            ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(it + 1, it1));
                        }
                    }
                    else if(v[3] == 1){
                        if(p.second == -p1.second){
                            int it = p.second;
                            if(it != v[1]){
                                ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(it - 1,it - 1));
                            }
                            if(it != v[2]){
                                temp.push_back({v[0] + cont * (it - v[1] + 1), it + 1, v[2],1});
                            }
                        }
                        else{
                            int it = -p1.second;
                            int it1 = p.second;

                            if(it != v[1]){
                                ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(it - 1,it - 1));
                            }
                            if(it1 != v[2]){
                                temp.push_back({v[0] + cont * (it1 - v[1] + 1), it1 + 1, v[2],1});
                            }
                            ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(it + 1, it1));
                        }
                    }
                    else{
                        if(p.second == -p1.second){
                            int it = p.second;
                            if(it != v[1]){
                                temp.push_back({v[0] + cont * (v[2] - it + 1), v[1], it - 1,2});
                            }
                            if(it != v[2]){
                                ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(v[2],v[2]));
                            }
                        }
                        else{
                            int it = -p1.second;
                            int it1 = p.second;

                            if(it != v[1]){
                                temp.push_back({v[0] + cont * (v[2] - it + 1), v[1], it - 1, 2});
                            }
                            if(it1 != v[2]){
                                ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(v[2],v[2]));
                            }
                            ans = min(ans, cont * (v[2] - v[1] + 1) + nodes[cont] -> query(it + 1, it1));
                        }
                    }

                    ans = min(ans + v[0],k);
                }

                v1 = temp;

                cont--;


            }
            banna.push_back(ans);
        }

        return banna;

    }
    else{
        for(int i = 0; i < N; i++){
            lst[i] = H[i];
        }

        build(1,0,N-1);

        vector<long long int> banna;

        for(int i = 0; i < Q; i++){
            int l,r;

            l = L[i];
            r = R[i];

            queue<vector<long long int>> pq;

            pq.push({0,l,r});

            long long int ans = 1e18;

            while(!pq.empty()){
                vector<long long int> v = pq.front();
                pq.pop();

                if(v[1] == v[2]){
                    ans = min(ans, v[0] + lst[v[1]]);
                    continue;
                }

                int it = query(1,0,N-1,v[1],v[2]).second;

                if(it != v[1]){
                    pq.push({lst[it] * (v[2] - it + 1) + v[0], v[1], it - 1 });
                }
            if(it != v[2]){
                pq.push({lst[it] * (it - v[1] + 1) + v[0], it + 1, v[2] });
            }
        }
        banna.push_back(ans);

        }
        return banna;
    }
}

Compilation message (stderr)

meetings.cpp: In function 'long long int recurse(int, int, int)':
meetings.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = 0; i < temp.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~~~~
meetings.cpp: In function 'std::pair<int, int> query(int, int, int, int, int)':
meetings.cpp:42:1: warning: control reaches end of non-void function [-Wreturn-type]
   42 | }
      | ^
meetings.cpp: In function 'std::pair<int, int> query1(int, int, int, int, int)':
meetings.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^

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