Submission #1308518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308518		thnhann	Mizuyokan 2 (JOI23_mizuyokan2)	C++20	0 / 100	100 ms	22088 KiB

mizuyokan2

#include <bits/stdc++.h>
using namespace std;

#define long long long

const int MAXN = 250005;
const int LOG = 19;
const long INF = 1e18;

int N, Q;
long L[MAXN];
long P[MAXN]; // Prefix sum

// Segment Tree để tìm chỉ số j nhỏ nhất thỏa mãn điều kiện 2
long tree[4 * MAXN];

void build(int node, int start, int end) {
    if (start == end) {
        // Lưu giá trị P[start-1] - d[start]
        // Lưu ý: start là index mảng d (1-based)
        tree[node] = P[start - 1] - L[start];
    } else {
        int mid = (start + end) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        tree[node] = max(tree[2 * node], tree[2 * node + 1]);
    }
}

// Tìm chỉ số nhỏ nhất trong đoạn [l, r] có giá trị > val
int query_first(int node, int start, int end, int l, int r, long val) {
    // Nếu đoạn không giao hoặc max value không đủ lớn
    if (start > end || start > r || end < l || tree[node] <= val) {
        return -1;
    }
    if (start == end) {
        return start;
    }
    int mid = (start + end) / 2;
    // Ưu tiên tìm bên trái trước (để lấy chỉ số nhỏ nhất)
    int res = query_first(2 * node, start, mid, l, r, val);
    if (res != -1) return res;
    return query_first(2 * node + 1, mid + 1, end, l, r, val);
}

int nxt[MAXN]; // Next valley index
int up[MAXN][LOG]; // Binary lifting table

// Hàm tính số bước nhảy từ u nhưng không vượt quá r
// Trả về số lượng mảnh *thêm vào* sau mảnh u
int calc_steps(int u, int r) {
    if (u > r) return 0;
    int steps = 0;
    int curr = u;

    // Nhảy doubling
    for (int k = LOG - 1; k >= 0; k--) {
        if (up[curr][k] <= r && up[curr][k] != N + 2) {
            curr = up[curr][k];
            steps += (1 << k);
        }
    }

    // steps tính số cặp (Peak, Valley).
    // Tổng số mảnh từ u đến curr là 1 (u) + 2 * steps.
    int pieces = 2 * steps;

    // Kiểm tra xem có thể tạo thêm 1 Đỉnh cuối cùng từ curr đến r không
    // Điều kiện: Sum(curr+1...r) > d[curr]
    if (P[r] - P[curr] > L[curr]) {
        pieces++;
    }

    return pieces;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N)) return 0;
    for (int i = 1; i <= N; i++) {
        cin >> L[i];
        P[i] = P[i - 1] + L[i];
    }

    build(1, 1, N);

    // Precompute next valley for every i
    for (int i = 1; i <= N; i++) {
        long val1 = P[i] + L[i];
        // Tìm k nhỏ nhất sao cho P[k] > P[i] + L[i]
        int k = upper_bound(P + 1, P + N + 1, val1) - P;

        // Cần tìm j >= k+1 sao cho P[j-1] - L[j] > P[i]
        int start_search = k + 1;
        int target_j = -1;

        if (start_search <= N) {
            target_j = query_first(1, 1, N, start_search, N, P[i]);
        }

        if (target_j != -1) {
            nxt[i] = target_j;
        } else {
            nxt[i] = N + 2; // Vô cực
        }
    }

    // Build Doubling Table
    // nxt[i] nhảy từ thung lũng i đến thung lũng tiếp theo (bỏ qua 1 đỉnh ở giữa)
    for (int i = 1; i <= N; i++) up[i][0] = nxt[i];
    for (int i = 0; i < LOG; i++) up[N + 1][i] = N + 2;
    for (int i = 0; i < LOG; i++) up[N + 2][i] = N + 2;

    for (int k = 1; k < LOG; k++) {
        for (int i = 1; i <= N; i++) {
            if (up[i][k - 1] <= N) {
                up[i][k] = up[up[i][k - 1]][k - 1];
            } else {
                up[i][k] = N + 2;
            }
        }
    }

    cin >> Q;
    while (Q--) {
        int X, A, B;
        long Y;
        cin >> X >> Y >> A >> B;
        // Subtask 4: Y = L[X], bỏ qua update, chỉ query

        int l = A + 1;
        int r = B;

        if (l > r) { // Trường hợp rỗng (không thể xảy ra theo đề bài A < B nhưng đề phòng)
            cout << 0 << "\n";
            continue;
        }

        // Cách 1: Bắt đầu bằng Thung lũng tại l
        // Độ dài = 1 (thung lũng l) + các bước nhảy
        int ans1 = 1 + calc_steps(l, r);

        // Cách 2: Bắt đầu bằng Đỉnh.
        // Ta cần tìm thung lũng đầu tiên j > l sao cho Đỉnh [l...j-1] > d[j]
        // Tức là tìm j nhỏ nhất thuộc [l+1, r] sao cho P[j-1] - d[j] > P[l-1]
        int first_valley = query_first(1, 1, N, l + 1, r, P[l - 1]);

        int ans2 = 0;
        if (first_valley != -1) {
            // Độ dài = 1 (Đỉnh đầu tiên) + 1 (thung lũng first_valley) + các bước nhảy
            ans2 = 2 + calc_steps(first_valley, r);
        } else {
            // Nếu không tìm được thung lũng nào để kết thúc cái đỉnh đầu tiên
            // Thì toàn bộ đoạn [l, r] là 1 đỉnh (hoặc 1 mảnh)
            ans2 = 1;
        }

        cout << max(ans1, ans2) << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11