Submission #1097782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097782		tien1710	Triple Jump (JOI19_jumps)	C++14	0 / 100	47 ms	4436 KiB

jumps

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Hàm đọc dữ liệu từ bàn phím
void readInput(int &N, vector<int> &cakes, int &M, vector<pair<int, int>> &requests) {
    cin >> N;
    cakes.resize(N);
    
    for (int i = 0; i < N; i++) {
        cin >> cakes[i];
    }
    
    cin >> M;
    requests.resize(M);
    
    for (int i = 0; i < M; i++) {
        int L, R;
        cin >> L >> R;
        requests[i] = {L - 1, R - 1}; // Chuyển về chỉ số mảng (giảm 1 để phù hợp với chỉ số 0-based)
    }
}

// Hàm giải quyết bài toán bằng cách tìm max bên trái và bên phải
vector<int> solveWithMaxArrays(int N, const vector<int> &cakes, int M, const vector<pair<int, int>> &requests) {
    // Tạo hai mảng phụ để lưu giá trị lớn nhất từ trái và phải
    vector<int> leftMax(N), rightMax(N);
    
    // Xây dựng mảng leftMax
    leftMax[0] = cakes[0];
    for (int i = 1; i < N; i++) {
        leftMax[i] = max(leftMax[i - 1], cakes[i]);
    }
    
    // Xây dựng mảng rightMax
    rightMax[N - 1] = cakes[N - 1];
    for (int i = N - 2; i >= 0; i--) {
        rightMax[i] = max(rightMax[i + 1], cakes[i]);
    }
    
    vector<int> results;
    
    // Xử lý từng yêu cầu
    for (const auto& request : requests) {
        int L = request.first;
        int R = request.second;
        
        // Tìm giá trị lớn nhất trong khoảng từ L đến R
        int maxVal = cakes[L]; // Bắt đầu với phần tử đầu tiên trong khoảng
        for (int i = L; i <= R; i++) {
            maxVal = max(maxVal, cakes[i]);
        }
        
        // Tìm tổng max từ L đến R
        results.push_back(maxVal);
    }
    
    return results;
}

int main() {
    int N, M;
    vector<int> cakes;
    vector<pair<int, int>> requests;
    
    // Nhập dữ liệu từ bàn phím
    readInput(N, cakes, M, requests);
    
    // Giải quyết bài toán
    vector<int> results = solveWithMaxArrays(N, cakes, M, requests);
    
    // In kết quả ra màn hình
    for (const int &result : results) {
        cout << result << endl;
    }

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54