Submission #1191835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191835		Joon_Yorigami	Horses (IOI15_horses)	C++20	100 / 100	732 ms	49176 KiB

horses

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

static const int MAXN = 500000;
static const int MOD  = 1000000007;

int N;
int Xarr[MAXN], Yarr[MAXN];
int prodSeg[4*MAXN], capSeg[4*MAXN];
int ySeg[4*MAXN];
int bestSeg[4*MAXN];
set<int> growths;

void buildProd(int node, int l, int r)
{
    if (l == r)
    {
        prodSeg[node] = Xarr[l] % MOD;
        capSeg[node]  = min(Xarr[l], 1000000000);
    }
    else
    {
        int mid = (l + r) >> 1;
        buildProd(node*2,   l,   mid);
        buildProd(node*2+1, mid+1, r);
        prodSeg[node] = int(1LL * prodSeg[node*2] * prodSeg[node*2+1] % MOD);
        capSeg[node]  = int(min(1000000000LL, 1LL * capSeg[node*2] * capSeg[node*2+1]));
    }
}

int queryProd(int seg[], int capArr[], int ql, int qr, bool capFlag, int node_l, int node_r, int node)
{
    if (qr < node_l || node_r < ql) return 1;
    if (ql <= node_l && node_r <= qr)
    {
        return capFlag ? capArr[node] : seg[node];
    }
    int mid = (node_l + node_r) >> 1;
    ll left  = queryProd(seg, capArr, ql, qr, capFlag, node_l,   mid, node*2);
    ll right = queryProd(seg, capArr, ql, qr, capFlag, mid+1, node_r, node*2+1);
    if (capFlag) return int(min(1000000000LL, left * right));
    return int((left * right) % MOD);
}

void updateProd(int seg[], int capArr[], int pos, int val, int node_l, int node_r, int node)
{
    if (node_l == node_r)
    {
        seg[node]    = val % MOD;
        capArr[node] = min(val, 1000000000);
    }
    else
    {
        int mid = (node_l + node_r) >> 1;
        if (pos <= mid)
            updateProd(seg, capArr, pos, val, node_l,   mid, node*2);
        else
            updateProd(seg, capArr, pos, val, mid+1, node_r, node*2+1);
        seg[node]    = int(1LL * seg[node*2] * seg[node*2+1] % MOD);
        capArr[node] = int(min(1000000000LL, 1LL * capArr[node*2] * capArr[node*2+1]));
    }
}

void buildY(int node, int l, int r)
{
    if (l == r)
    {
        ySeg[node] = l;
    }
    else
    {
        int mid = (l + r) >> 1;
        buildY(node*2,   l,   mid);
        buildY(node*2+1, mid+1, r);
        int a = ySeg[node*2], b = ySeg[node*2+1];
        ySeg[node] = (Yarr[a] >= Yarr[b] ? a : b);
    }
}

void updateYseg(int node, int l, int r, int pos)
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid)
    {
        updateYseg(node*2,   l,   mid, pos);
    }
    else
    {
        updateYseg(node*2+1, mid+1, r, pos);
    }
    int a = ySeg[node*2], b = ySeg[node*2+1];
    ySeg[node] = (Yarr[a] >= Yarr[b] ? a : b);
}

void buildBest(int node, int l, int r)
{
    if (l == r)
    {
        bestSeg[node] = l;
    }
    else
    {
        int mid = (l + r) >> 1;
        buildBest(node*2,   l,   mid);
        buildBest(node*2+1, mid+1, r);
        int L = bestSeg[node*2], R = bestSeg[node*2+1];
        ll cap  = queryProd(prodSeg, capSeg, L+1, R, true, 0, N-1, 1);
        ll need = (Yarr[L] + Yarr[R] - 1LL) / Yarr[R];
        bestSeg[node] = (cap >= need ? R : L);
    }
}

void updateBest(int node, int l, int r, int pos)
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid)
    {
        updateBest(node*2,   l,   mid, pos);
    }
    else
    {
        updateBest(node*2+1, mid+1, r, pos);
    }
    int L = bestSeg[node*2], R = bestSeg[node*2+1];
    ll cap  = queryProd(prodSeg, capSeg, L+1, R, true, 0, N-1, 1);
    ll need = (Yarr[L] + Yarr[R] - 1LL) / Yarr[R];
    bestSeg[node] = (cap >= need ? R : L);
}

int init(int NN, int X[], int Y[])
{
    N = NN;
    for (int i = 0; i < N; i++)
    {
        Xarr[i] = X[i];
        Yarr[i] = Y[i];
        if (Xarr[i] != 1) growths.insert(i);
    }
    growths.insert(0);
    buildProd(1, 0, N-1);
    buildY(1, 0, N-1);
    buildBest(1, 0, N-1);
    int idx = bestSeg[1];
    return int(1LL * queryProd(prodSeg, capSeg, 0, idx, false, 0, N-1, 1) * Yarr[idx] % MOD);
}

int updateX(int pos, int val)
{
    Xarr[pos] = val;
    if (val == 1 && pos != 0) growths.erase(pos);
    else growths.insert(pos);
    updateProd(prodSeg, capSeg, pos, val, 0, N-1, 1);
    updateBest(1, 0, N-1, pos);
    int idx = bestSeg[1];
    return int(1LL * queryProd(prodSeg, capSeg, 0, idx, false, 0, N-1, 1) * Yarr[idx] % MOD);
}

int updateY(int pos, int val)
{
    Yarr[pos] = val;
    updateYseg(1, 0, N-1, pos);
    updateBest(1, 0, N-1, pos);
    int idx = bestSeg[1];
    return int(1LL * queryProd(prodSeg, capSeg, 0, idx, false, 0, N-1, 1) * Yarr[idx] % MOD);
}

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