제출 #1310047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310047		muhammad-ahmad	말 (IOI15_horses)	C++20	100 / 100	551 ms	45116 KiB

horses

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

typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 500005;

int n;
int curX[MAXN], curY[MAXN];
ll treeX[4 * MAXN];
int treeY[4 * MAXN];
set<int> st;

// Segment Tree for Product of X (modulo 10^9 + 7)
void buildX(int node, int start, int end) {
    if (start == end) {
        treeX[node] = curX[start];
        return;
    }
    int mid = (start + end) / 2;
    buildX(2 * node, start, mid);
    buildX(2 * node + 1, mid + 1, end);
    treeX[node] = (treeX[2 * node] * treeX[2 * node + 1]) % MOD;
}

void updX(int node, int start, int end, int idx, int val) {
    if (start == end) {
        treeX[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) updX(2 * node, start, mid, idx, val);
    else updX(2 * node + 1, mid + 1, end, idx, val);
    treeX[node] = (treeX[2 * node] * treeX[2 * node + 1]) % MOD;
}

ll queryX(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 1;
    if (l <= start && end <= r) return treeX[node];
    int mid = (start + end) / 2;
    return (queryX(2 * node, start, mid, l, r) * queryX(2 * node + 1, mid + 1, end, l, r)) % MOD;
}

// Segment Tree for Maximum of Y
void buildY(int node, int start, int end) {
    if (start == end) {
        treeY[node] = curY[start];
        return;
    }
    int mid = (start + end) / 2;
    buildY(2 * node, start, mid);
    buildY(2 * node + 1, mid + 1, end);
    treeY[node] = max(treeY[2 * node], treeY[2 * node + 1]);
}

void updY(int node, int start, int end, int idx, int val) {
    if (start == end) {
        treeY[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) updY(2 * node, start, mid, idx, val);
    else updY(2 * node + 1, mid + 1, end, idx, val);
    treeY[node] = max(treeY[2 * node], treeY[2 * node + 1]);
}

int queryY(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return treeY[node];
    int mid = (start + end) / 2;
    return max(queryY(2 * node, start, mid, l, r), queryY(2 * node + 1, mid + 1, end, l, r));
}

int solve() {
    // Collect last ~30 positions where X[i] > 1
    vector<int> pos;
    auto it = st.end();
    ll prod = 1;
    for (int i = 0; i < 35 && it != st.begin(); i++) {
        it--;
        pos.push_back(*it);
        prod *= curX[*it];
        if (prod > 2e9) break; // Optimization: past 10^9, previous years can't win
    }
    reverse(pos.begin(), pos.end());

    // Candidates for best selling year
    int best_pos_idx = -1; // -1 represents the interval before the first X > 1
    int cur_best_y = (pos.empty() ? queryY(1, 0, n - 1, 0, n - 1) : queryY(1, 0, n - 1, 0, pos[0] - 1));

    for (int i = 0; i < (int)pos.size(); i++) {
        int L = pos[i];
        int R = (i + 1 < (int)pos.size()) ? pos[i + 1] - 1 : n - 1;
        int m_i = queryY(1, 0, n - 1, L, R);

        ll p = 1;
        int start_search = (best_pos_idx == -1) ? 0 : best_pos_idx + 1;
        for (int k = start_search; k <= i; k++) {
            p *= curX[pos[k]];
            if (p > 2e9) break;
        }

        if (p >= 2e9 || p * m_i >= cur_best_y) {
            cur_best_y = m_i;
            best_pos_idx = i;
        }
    }

    ll ans_prod = 1;
    if (best_pos_idx != -1) ans_prod = queryX(1, 0, n - 1, 0, pos[best_pos_idx]);
    return (ans_prod * cur_best_y) % MOD;
}

int init(int N, int X[], int Y[]) {
    n = N;
    for (int i = 0; i < n; i++) {
        curX[i] = X[i];
        curY[i] = Y[i];
        if (X[i] > 1) st.insert(i);
    }
    buildX(1, 0, n - 1);
    buildY(1, 0, n - 1);
    return solve();
}

int updateX(int pos, int val) {
    if (curX[pos] > 1) st.erase(pos);
    curX[pos] = val;
    if (curX[pos] > 1) st.insert(pos);
    updX(1, 0, n - 1, pos, val);
    return solve();
}

int updateY(int pos, int val) {
    curY[pos] = val;
    updY(1, 0, n - 1, pos, val);
    return solve();
}

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