oj.uz

Submission #944062

# Submission time Handle Problem Language Result Execution time Memory
944062 2024-03-12T07:56:08 Z salmon Meetings (IOI18_meetings) C++14
0 / 100
 19 ms 4692 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++){
        scanf(" %d",&l);
        scanf(" %d",&r);

        priority_queue<vector<long long int>,vector<vector<long long int>>,greater<vector<long long int>>> pq;

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

        long long int ans = 1e18;

        while(!pq.empty()){
            vector<long long int> v = pq.top();
            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] * (it - v[1] + 1) + v[0], it + 1, v[2] });
            }
            if(it != v[2]){
                pq.push({lst[it] * (v[2] - it + 1) + v[0], v[1], it - 1 });
            }
        }
        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 | }
      | ^
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf(" %d",&l);
      |         ~~~~~^~~~~~~~~~
meetings.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf(" %d",&r);
      |         ~~~~~^~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 19 ms 4692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 19 ms 4692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -