제출 #1191723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191723		burgerguy	Horses (IOI15_horses)	C++20	17 / 100	351 ms	44372 KiB

horses

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll MOD = 1e9 + 7;

ll n;

vector<ll> x,y;
vector<ll> horses(4 * 500010), segTree(4 * 500010);

void buildHorses(ll curNode, ll leftPointer, ll rightPointer) {
    if(leftPointer == rightPointer) horses[curNode] = x[leftPointer];
    else {
        ll midPointer = (leftPointer + rightPointer)/2;

        buildHorses(curNode * 2, leftPointer, midPointer);
        buildHorses(curNode * 2 + 1, midPointer + 1, rightPointer);

        horses[curNode] = (horses[curNode * 2] * horses[curNode * 2 + 1]) % MOD;
    }
}

void updateHorses(ll curNode, ll leftPointer, ll rightPointer, ll pos, ll newVal) {
    if(leftPointer == rightPointer && leftPointer == pos) horses[pos] = newVal;
    else {
        ll midPointer = (leftPointer + rightPointer)/2;

        if(midPointer >= pos) updateHorses(curNode * 2, leftPointer, midPointer, pos, newVal);
        else updateHorses(curNode * 2 + 1, midPointer + 1, rightPointer, pos, newVal);

        horses[curNode] = (horses[curNode * 2] * horses[curNode * 2 + 1]) % MOD;
    }
}

ll getHorses(ll curNode, ll leftPointer, ll rightPointer, ll leftBoundary, ll rightBoundary) {
    if(leftBoundary > rightBoundary) return 1;
    if(leftPointer == leftBoundary && rightPointer == rightBoundary) return horses[curNode];

    ll midPointer = (leftPointer + rightPointer)/2;

    return (getHorses(curNode * 2, leftPointer, midPointer, leftBoundary, min(midPointer, rightBoundary)) *
            getHorses(curNode * 2 + 1, midPointer + 1, rightPointer, max(leftBoundary, midPointer + 1), rightBoundary)) % MOD;
}

void build(ll curNode, ll leftPointer, ll rightPointer) {
    if(leftPointer == rightPointer) segTree[curNode] = (x[leftPointer] * y[leftPointer]) % MOD;
    else {
        ll midPointer = (leftPointer + rightPointer)/2;

        build(curNode * 2, leftPointer, midPointer);
        build(curNode * 2 + 1, midPointer + 1, rightPointer);

        segTree[curNode] = (max(segTree[curNode * 2],
                                (getHorses(1, 0, n, leftPointer, midPointer) * segTree[curNode * 2 + 1]) % MOD)) % MOD;
    }
}

void update(ll curNode, ll leftPointer, ll rightPointer, ll pos, ll newVal) {
    if(leftPointer == rightPointer && leftPointer == pos) {
        segTree[curNode] = x[leftPointer] * newVal;
        y[pos] = newVal;
    }
    else {
        ll midPointer = (leftPointer + rightPointer)/2;

        if(midPointer >= pos) update(curNode * 2, leftPointer, midPointer, pos, newVal);
        else update(curNode * 2 + 1, midPointer + 1, rightPointer, pos, newVal);

        segTree[curNode] = (max(segTree[curNode * 2],
                                (getHorses(1, 0, n, leftPointer, midPointer) * segTree[curNode * 2 + 1]) % MOD)) % MOD;
    }
}

int init(int N, int X[], int Y[]) {
    n = N - 1;

    for (int i = 0; i < N; ++i) {
        x.push_back(X[i]);
        y.push_back(Y[i]);
    }

    buildHorses(1, 0, n);
    build(1, 0, n);

    return segTree[1];
}

int updateX(int pos, int val) {
    updateHorses(1, 0, n, pos, val);
    update(1, 0, n, pos, y[pos]);

    return segTree[1];
}

int updateY(int pos, int val) {
    update(1, 0, n, pos, val);

    return segTree[1];
}
//
//
//int main() {
//    ll t; cin >> t;
//    int a[t], b[t];
//
//    for (int i = 0; i < t; ++i) {
//        cin >> a[i];
//    }
//    for (int i = 0; i < t; ++i) {
//        cin >> b[i];
//    }
//
//    init(t, a, b);
//
//    ll m; cin >> m;
//    while(m--) {
//        ll q,w,e; cin >> q >> w >> e;
//
//        if(q == 1) cout << updateX(w,e);
//        else cout << updateY(w,e);
//
//        cout << '\n';
//    }
//}

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