Submission #1147071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147071		heeheeheehaaw	Horses (IOI15_horses)	C++20	17 / 100	1597 ms	43868 KiB

horses

#include <bits/stdc++.h>
#define int long long
#include "horses.h"

using namespace std;

int aint[2000005];
const int mod = 1e9 + 7;
int n;
int x[500005], y[500005];
int prod = 1;
set<int> s;

int put(int n, int k)
{
    if(k == 0) return 1;
    if(k % 2 == 1) return put(n * n % mod, k / 2) * n % mod;
    return put(n * n % mod, k / 2);
}

void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod] = y[st];
        return;
    }

    int mij = (st + dr) / 2;
    build(nod * 2, st, mij);
    build(nod * 2 + 1, mij + 1, dr);
    aint[nod] = max(aint[nod * 2], aint[nod * 2 + 1]);
}

void update(int nod, int st, int dr, int poz, int val)
{
    if(st == dr)
    {
        aint[nod] = val;
        return;
    }

    int mij = (st + dr) / 2;
    update(nod * 2, st, mij, poz, val);
    update(nod * 2 + 1, mij + 1, dr, poz, val);
    aint[nod] = max(aint[nod * 2], aint[nod * 2 + 1]);
}

int query(int nod, int st, int dr, int le, int ri)
{
    if(le > ri) return 0;
    if(st == le && dr == ri)
        return aint[nod];
    int mij = (st + dr) / 2;
    return max(query(nod * 2, st, mij, le, min(ri, mij)),
               query(nod * 2 + 1, mij + 1, dr, max(le, mij + 1), ri));
}

int inv(int x)
{
    return put(x, mod - 2);
}

int32_t solve()
{
    s.insert(1);
    auto it = s.end();
    int currprod = 1, rez = 0;
    vector<int> p;
    while(it != s.begin() && currprod <= 1000000000LL)
    {
        it--;
        p.push_back(*it);
        currprod *= x[p.back()];
    }

    currprod /= x[p.back()];
    reverse(p.begin(), p.end());
    int prodpref = 1;
    for(auto i : p)
    {
        if(i != p[0])
            prodpref *= x[i];
        int by = query(1, 1, n, max(i, 1LL), n);
        rez = max(rez, by * prodpref);
    }

    rez %= mod;
    return (int32_t)((int)(prod * inv(currprod) % mod * (rez % mod) % mod));
}

int32_t updateX(int32_t poz, int32_t val)
{
    poz++;
    prod = prod * inv(x[poz]) % mod;
    prod = prod * val % mod;
    if(x[poz] == 1)
    {
        if(val > 1)
        {
            s.insert(poz);
        }
    }
    else
    {
        if(val == 1)
            s.erase(s.find(poz));
    }

    x[poz] = val;
    return solve();
}

int32_t updateY(int32_t poz, int32_t val)
{
    poz++;
    y[poz] = val;
    update(1, 1, n, poz, val);
    return solve();
}

int32_t init(int32_t N, int32_t X[], int32_t Y[])
{
    n = N;
    s.clear();
    prod = 1;
    for(int i = 0; i < n; i++)
    {
        x[i + 1] = X[i];
        y[i + 1] = Y[i];
        prod = prod * x[i + 1] % mod;
        if(x[i + 1] > 1)
            s.insert(i + 1);
    }

    x[0] = 1;
    y[0] = 1;
    //s.insert(0);
    build(1, 1, n);
    return solve();
}

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