제출 #944067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944067		salmon	모임들 (IOI18_meetings)	C++14	19 / 100	5559 ms	3920 KiB

meetings

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40