제출 #1147037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147037		heeheeheehaaw	말 (IOI15_horses)	C++20	0 / 100	1600 ms	43872 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 aib[500005], 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()
{
    auto it = s.end();
    int pasi = 31, last = n, currprod = 1, rez = -1, prd = -1;
    while(pasi--)
    {
        if(*it == 0)
            break;
        it = prev(it);
        int i = *it;
        if(currprod >= 1000000000)
            break;
        int by = query(1, 1, n, max(1LL, i), last);
        if(rez == -1) rez = i, prd = currprod;
        else
        {
            int prefprod = prod * inv(currprod) % mod;
            int prefrezprod = prod * inv(prd) % mod;
            prefrezprod = prefrezprod * inv(prefprod) % mod;
            if(prefrezprod * y[rez] < by)
                rez = i, prd = currprod;
        }

        currprod = currprod * x[i];
    }

    return prod * inv(prd) % mod * y[rez] % 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);
            x[poz] = val;
        }
    }
    else
    {
        if(val == 1)
            s.erase(poz);
        x[poz] = val;
    }

    return solve();
}

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

int32_t init(int32_t N, int32_t X[], int32_t Y[])
{
    n = N;
    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: 0 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23