Submission #1248771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248771		KindaGoodGames	Horses (IOI15_horses)	C++20	17 / 100	1595 ms	20292 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define int long long

const int MOD = 1e9 + 7;

struct SegmentTreeMax {
    vector<int> S;
    int len = 1;
    SegmentTreeMax(int n) {
        while (len < n) len <<= 1;
        S.resize(2 * len);
    }
    SegmentTreeMax() {}

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

    void upd(int pos, int val) {
        pos += len;
        S[pos] = val;
        for (pos /= 2; pos > 0; pos /= 2) {
            S[pos] = max(S[pos * 2], S[pos * 2 + 1]);
        }
    }
};

int n;
vector<int> X;
vector<int> Y;
SegmentTreeMax segY;

int solve() {
    int prod = 1;
    int res = 0;
    for (int i = 0; i < n; i++) {
        prod = (prod * X[i]) % MOD;
        int coef = segY.query(i, n);  // max Y[j] where j >= i
        res = max(res, (prod * coef) % MOD);
    }
    return res;
}

int32_t init(int32_t N, int32_t mult[], int32_t cost[]) {
    n = N;
    X = vector<int>(n);
    Y = vector<int>(n);
    segY = SegmentTreeMax(n);

    for (int i = 0; i < n; i++) {
        X[i] = mult[i];
        Y[i] = cost[i];
        segY.upd(i, Y[i]);
    }

    return solve();
}

int32_t updateX(int32_t pos, int32_t val) {
    X[pos] = val;
    return solve();
}

int32_t updateY(int32_t pos, int32_t val) {
    Y[pos] = val;
    segY.upd(pos, val);
    return solve();
}

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