oj.uz

Submission #944067

# Submission time Handle Problem Language Result Execution time Memory
944067 2024-03-12T08:00:18 Z salmon Meetings (IOI18_meetings) C++14
19 / 100
 5500 ms 3920 KB 
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;

int N;
int Q;
int lst[750100];
int l, r;
pair<int,int> st[3100100];

void build(int i, int s, int e){
    if(s == e){
        st[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]);
}

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);
}



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

    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++){
        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 'std::pair<int, int> query(int, int, int, int, int)':
meetings.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 2 ms 2592 KB Output is correct
3 Correct 4 ms 2396 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2532 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 5 ms 2396 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 2 ms 2592 KB Output is correct
3 Correct 4 ms 2396 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2532 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 5 ms 2396 KB Output is correct
10 Correct 816 ms 3112 KB Output is correct
11 Correct 2434 ms 3168 KB Output is correct
12 Correct 801 ms 3156 KB Output is correct
13 Correct 2530 ms 2848 KB Output is correct
14 Correct 777 ms 2932 KB Output is correct
15 Correct 674 ms 3032 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Execution timed out 5559 ms 3920 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Execution timed out 5559 ms 3920 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 2 ms 2592 KB Output is correct
3 Correct 4 ms 2396 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2532 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 5 ms 2396 KB Output is correct
10 Correct 816 ms 3112 KB Output is correct
11 Correct 2434 ms 3168 KB Output is correct
12 Correct 801 ms 3156 KB Output is correct
13 Correct 2530 ms 2848 KB Output is correct
14 Correct 777 ms 2932 KB Output is correct
15 Correct 674 ms 3032 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Execution timed out 5559 ms 3920 KB Time limit exceeded
18 Halted 0 ms 0 KB -