Submission #1191783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191783		burgerguy	Horses (IOI15_horses)	C++20	100 / 100	646 ms	138604 KiB

horses

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll MOD = 1e9 + 7;
ll n;

vector<ll> x,y;

struct Node {
    ll mod;
    long double log;
};

Node mergeHorses(Node &a, Node &b) {
    return {(a.mod * b.mod) % MOD, a.log + b.log};
}

Node merge(Node &a, Node &b, Node &horses) {
    long double bLog = horses.log + b.log;
    ll bMod = (horses.mod * b.mod) % MOD;

    if (a.log > bLog) return a;
    else return {bMod, bLog};
}

vector<Node> horses(4 * 500010), segTree(4 * 500010);

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

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

        horses[curNode] = mergeHorses(horses[curNode * 2], horses[curNode * 2 + 1]);
    }
}

void updateHorses(ll curNode, ll leftPointer, ll rightPointer, ll pos, ll newVal) {
    if(leftPointer == rightPointer && leftPointer == pos) {
        horses[curNode] = {newVal, log(newVal)};
        x[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] = mergeHorses(horses[curNode * 2], horses[curNode * 2 + 1]);
    }
}

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

    ll midPointer = (leftPointer + rightPointer)/2;

    Node left = getHorses(curNode * 2, leftPointer, midPointer, leftBoundary, min(midPointer, rightBoundary));
    Node right = getHorses(curNode * 2 + 1, midPointer + 1, rightPointer, max(leftBoundary, midPointer + 1), rightBoundary);

    return mergeHorses(left, right);
}

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

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

        Node addHorses = getHorses(1, 0, n, leftPointer, midPointer);
        segTree[curNode] = merge(segTree[curNode * 2],segTree[curNode * 2 + 1], addHorses);
    }
}

void update(ll curNode, ll leftPointer, ll rightPointer, ll pos, ll newVal) {
    if(leftPointer == rightPointer && leftPointer == pos) {
        segTree[curNode] = {(x[leftPointer] * newVal) % MOD, log(x[leftPointer]) + log(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);

        Node addHorses = getHorses(1, 0, n, leftPointer, midPointer);
        segTree[curNode] = merge(segTree[curNode * 2],segTree[curNode * 2 + 1], addHorses);
    }
}

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].mod;
}

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

    return segTree[1].mod;
}

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

    return segTree[1].mod;
}

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