oj.uz

Submission #944776

# Submission time Handle Problem Language Result Execution time Memory
944776 2024-03-13T04:39:20 Z salmon Meetings (IOI18_meetings) C++14
60 / 100
 2514 ms 298212 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 4 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 4 ms 4444 KB Output is correct
6 Correct 2 ms 4640 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 5 ms 4440 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 4 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 4 ms 4444 KB Output is correct
6 Correct 2 ms 4640 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 5 ms 4440 KB Output is correct
10 Correct 822 ms 4948 KB Output is correct
11 Correct 2514 ms 5220 KB Output is correct
12 Correct 801 ms 5016 KB Output is correct
13 Correct 2492 ms 5012 KB Output is correct
14 Correct 770 ms 4944 KB Output is correct
15 Correct 665 ms 5032 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 239 ms 31244 KB Output is correct
3 Correct 843 ms 297952 KB Output is correct
4 Correct 940 ms 298160 KB Output is correct
5 Correct 482 ms 297860 KB Output is correct
6 Correct 756 ms 298000 KB Output is correct
7 Correct 827 ms 298176 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 239 ms 31244 KB Output is correct
3 Correct 843 ms 297952 KB Output is correct
4 Correct 940 ms 298160 KB Output is correct
5 Correct 482 ms 297860 KB Output is correct
6 Correct 756 ms 298000 KB Output is correct
7 Correct 827 ms 298176 KB Output is correct
8 Correct 1124 ms 297760 KB Output is correct
9 Correct 756 ms 297676 KB Output is correct
10 Correct 1177 ms 297824 KB Output is correct
11 Correct 1312 ms 297932 KB Output is correct
12 Correct 838 ms 297832 KB Output is correct
13 Correct 1239 ms 297720 KB Output is correct
14 Correct 547 ms 297860 KB Output is correct
15 Correct 1942 ms 298212 KB Output is correct
16 Correct 1004 ms 298008 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 4 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 4 ms 4444 KB Output is correct
6 Correct 2 ms 4640 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 5 ms 4440 KB Output is correct
10 Correct 822 ms 4948 KB Output is correct
11 Correct 2514 ms 5220 KB Output is correct
12 Correct 801 ms 5016 KB Output is correct
13 Correct 2492 ms 5012 KB Output is correct
14 Correct 770 ms 4944 KB Output is correct
15 Correct 665 ms 5032 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 239 ms 31244 KB Output is correct
18 Correct 843 ms 297952 KB Output is correct
19 Correct 940 ms 298160 KB Output is correct
20 Correct 482 ms 297860 KB Output is correct
21 Correct 756 ms 298000 KB Output is correct
22 Correct 827 ms 298176 KB Output is correct
23 Correct 1124 ms 297760 KB Output is correct
24 Correct 756 ms 297676 KB Output is correct
25 Correct 1177 ms 297824 KB Output is correct
26 Correct 1312 ms 297932 KB Output is correct
27 Correct 838 ms 297832 KB Output is correct
28 Correct 1239 ms 297720 KB Output is correct
29 Correct 547 ms 297860 KB Output is correct
30 Correct 1942 ms 298212 KB Output is correct
31 Correct 1004 ms 298008 KB Output is correct
32 Runtime error 196 ms 60244 KB Execution killed with signal 11
33 Halted 0 ms 0 KB -