제출 #1315496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315496		idk_anything_i_guess	Horses (IOI15_horses)	C++20	17 / 100	295 ms	40704 KiB

horses

#include <bits/stdc++.h>

using namespace std;

// Constants and Globals
const int MOD = 1e9 + 7;
const int MAXN = 500005;

int n;
int x[MAXN], y[MAXN];
set<int> s; // Stores indices where x[i] > 1

// Segment Tree for Product of X (Modulo 1e9+7)
struct TreeX {
    int t[4 * MAXN];

    void build(int i, int l, int r) {
        if (l == r) {
            t[i] = x[l] % MOD;
            return;
        }
        int m = (l + r) >> 1;
        build(2 * i, l, m);
        build(2 * i + 1, m + 1, r);
        t[i] = (1LL * t[2 * i] * t[2 * i + 1]) % MOD;
    }

    void update(int i, int l, int r, int p, int v) {
        if (l == r) {
            t[i] = v % MOD;
            return;
        }
        int m = (l + r) >> 1;
        if (p <= m) update(2 * i, l, m, p, v);
        else update(2 * i + 1, m + 1, r, p, v);
        t[i] = (1LL * t[2 * i] * t[2 * i + 1]) % MOD;
    }

    int query(int i, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return 1;
        if (ql <= l && r <= qr) return t[i];
        int m = (l + r) >> 1;
        return (1LL * query(2 * i, l, m, ql, qr) * query(2 * i + 1, m + 1, r, ql, qr)) % MOD;
    }
} st_x;

// Segment Tree for Maximum Y
struct TreeY {
    int t[4 * MAXN];

    void build(int i, int l, int r) {
        if (l == r) {
            t[i] = y[l];
            return;
        }
        int m = (l + r) >> 1;
        build(2 * i, l, m);
        build(2 * i + 1, m + 1, r);
        t[i] = max(t[2 * i], t[2 * i + 1]);
    }

    void update(int i, int l, int r, int p, int v) {
        if (l == r) {
            t[i] = v;
            return;
        }
        int m = (l + r) >> 1;
        if (p <= m) update(2 * i, l, m, p, v);
        else update(2 * i + 1, m + 1, r, p, v);
        t[i] = max(t[2 * i], t[2 * i + 1]);
    }

    int query(int i, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return 0;
        if (ql <= l && r <= qr) return t[i];
        int m = (l + r) >> 1;
        return max(query(2 * i, l, m, ql, qr), query(2 * i + 1, m + 1, r, ql, qr));
    }
} st_y;

// Core logic to find the maximum profit
int solve() {
    vector<int> idx;
    auto it = s.rbegin();
    
    // 1. Gather relevant indices from right to left
    // We only need enough X's such that their product exceeds 1e9, 
    // because Max(Y) is 1e9. Older X's would just make the prefix multiplier huge.
    long long cur_check = 1;
    while (it != s.rend()) {
        idx.push_back(*it);
        cur_check *= x[*it];
        // 1e9 + 7 is a safe upper bound check to cover Max Y range
        if (cur_check > 1000000007) break; 
        it++;
    }
    // Always consider the start of the array to cover the range [0, first_non_one)
    if (idx.empty() || idx.back() != 0) idx.push_back(0);
    
    reverse(idx.begin(), idx.end());
    
    long long best_val = -1;
    long long cur_prod = 1; // Stores accumulated X within the window
    
    // 2. Iterate through the window of indices
    for (size_t i = 0; i < idx.size(); i++) {
        int p = idx[i];
        // The current block ends before the next interesting index, or at the end of array
        int r = (i + 1 < idx.size()) ? idx[i+1] - 1 : n - 1;
        
        // Multiply by X at the current start position
        cur_prod *= x[p]; 
        
        // Find max Y in this block [p, r]
        // Note: X values from p+1 to r are all 1, so cur_prod is valid for the whole range
        int max_y_in_range = st_y.query(1, 0, n - 1, p, r);
        
        // Compare relative profit
        if (cur_prod * max_y_in_range > best_val) {
            best_val = cur_prod * max_y_in_range;
        }
    }
    
    // 3. Calculate final result modulo 1e9+7
    // Result = (PrefixProduct_Before_Window * Best_Relative_Value) % MOD
    long long prefix_prod = st_x.query(1, 0, n - 1, 0, idx[0] - 1);
    long long ans = (prefix_prod * (best_val % MOD)) % MOD;
    
    return (int)ans;
}

int init(int N, int X[], int Y[]) {
    n = N;
    for (int i = 0; i < n; i++) {
        x[i] = X[i];
        y[i] = Y[i];
        if (x[i] > 1) s.insert(i);
    }
    
    st_x.build(1, 0, n - 1);
    st_y.build(1, 0, n - 1);
    
    return solve();
}

int updateX(int pos, int val) {
    if (x[pos] > 1) s.erase(pos);
    x[pos] = val;
    if (x[pos] > 1) s.insert(pos);
    
    st_x.update(1, 0, n - 1, pos, val);
    return solve();
}

int updateY(int pos, int val) {
    y[pos] = val;
    st_y.update(1, 0, n - 1, pos, val);
    return solve();
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23