let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

KAGAIN - Chiến trường Ô qua

solution.md

Bài này cần tính \(L[i]\) là chỉ số lớn nhất ở bên trái \(i\) sao cho \(A[L[i]] < A[i]\). R[i] là chỉ số bé nhất ở bên phải sao cho \(A[R[i]] < A[i]\). L và R được tính bằng kĩ thuật Deque, xem tài liệu ở trên.

Sau đó tìm vị trí \(i\) có \(A[i]*(R[i] - L[i] + 1)\) lớn nhất.

deque

Hình minh họa

main.cpp
Open in Github Download
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<int> a(n);
        for (int &x: a) cin >> x;
        vector<int> l(n), r(n);
        vector<int> stack;
        for (int i=0; i<n; i++) {
            while (!stack.empty() && a[stack.back()] >= a[i]) stack.pop_back();
            if (stack.empty()) l[i] = -1;
            else l[i] = stack.back();
            stack.push_back(i);
        }
        stack.clear();
        for (int i = n-1; i>=0; i--) {
            while (!stack.empty() && a[stack.back()] >= a[i]) stack.pop_back();
            if (stack.empty()) r[i] = n;
            else r[i] = stack.back();
            stack.push_back(i);
        }
#define res(i) (a[i]*(r[i]-l[i]-1))
        int u = 0;
        for (int i=1; i<n; i++) if (res(u) < res(i)) u = i;
        cout << res(u) << ' ' << l[u] + 2 << ' ' << r[u] << '\n';

    }
    return 0;
}
Comments