oj.uz

Submission #1097782

# Submission time Handle Problem Language Result Execution time Memory
1097782 2024-10-08T09:18:42 Z tien1710 Triple Jump (JOI19_jumps) C++14
0 / 100
 47 ms 4436 KB 
#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.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 4436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

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