Submission #1059055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059055		andrei_iorgulescu	Horses (IOI15_horses)	C++14	17 / 100	1295 ms	86608 KiB

horses

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

using namespace std;

using ll = long long;

int modulo = (int)1e9 + 7;

int lgpow(int lul1, int lul2)
{
    int lul3 = 1;
    while (lul2 != 0)
    {
        if (lul2 % 2 == 1)
            lul3 = 1ll * lul3 * lul1 % modulo;
        lul1 = 1ll * lul1 * lul1 % modulo;
        lul2 /= 2;
    }
    return lul3;
}

int x[500005], y[500005];
int n;
set<int> grx;
int aint[2000005];
ll allx = 1;

void build(int nod, int l, int r)
{
    if (l == r)
        aint[nod] = y[l];
    else
    {
        int mij = (l + r) / 2;
        build(2 * nod,l,mij);
        build(2 * nod + 1,mij + 1,r);
        aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
    }
}

void update(int nod, int l, int r, int pos, int val)
{
    if (l == r)
        aint[nod] = val;
    else
    {
        int mij = (l + r) / 2;
        if (pos <= mij)
            update(2 * nod,l,mij,pos,val);
        else
            update(2 * nod + 1,mij + 1,r,pos,val);
        aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
    }
}

int query(int nod, int l, int r, int st, int dr)
{
    if (r < st or dr < l)
        return 0;
    if (st <= l and r <= dr)
        return aint[nod];
    int mij = (l + r) / 2;
    return max(query(2 * nod,l,mij,st,dr), query(2 * nod + 1,mij + 1,r,st,dr));
}

int solve()
{
    vector<pair<ll, pair<int,int>>> candi;
    vector<int> depus;
    ll prd = 1;
    int r = n;
    while (!grx.empty() and prd < (int)1e9)
    {
        int l = *grx.rbegin();
        candi.push_back({x[l], {l,r}});
        depus.push_back(l);
        grx.erase(l);
        prd *= (ll)x[l];
        r = l - 1;
    }
    if (prd < (int)1e9 and r >= 1)
        candi.push_back({1,{1,r}});
    reverse(candi.begin(),candi.end());
    for (int i = 0; i + 1 < candi.size(); i++)
        candi[i + 1].first *= candi[i].first;
    __int128 ans = 0;
    for (auto it : candi)
    {
        __int128 prr = it.first;
        __int128 prr2 = query(1,1,n,it.second.first,it.second.second);
        prr *= prr2;
        ans = max(ans,prr);
    }
    for (auto it : depus)
        grx.insert(it);
    ans %= modulo;
    ans = ans * allx % modulo;
    prd %= modulo;
    ans = ans * lgpow(prd, modulo - 2) % modulo;
    return ans;
}

int init(int N, int X[], int Y[])
{
    n = N;
    for (int i = 1; i <= n; i++)
        x[i] = X[i - 1], y[i] = Y[i - 1];
    for (int i = 1; i <= n; i++)
        if (x[i] > 1)
            grx.insert(i), allx = allx * x[i] % modulo;
    build(1,1,n);
    return solve();
}

int updateX(int pos, int val)
{
    pos++;
    allx *= lgpow(x[pos], modulo - 2);
    allx %= modulo;
    if (x[pos] > 1)
        grx.erase(pos);
    x[pos] = val;
    if (x[pos] > 1)
        grx.insert(val);
    allx = allx * val % modulo;
    return solve();
}

int updateY(int pos, int val)
{
    pos++;
    update(1,1,n,pos,val);
    return solve();
}

Compilation message (stderr)

horses.cpp: In function 'int lgpow(int, int)':
horses.cpp:16:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |             lul3 = 1ll * lul3 * lul1 % modulo;
      |                    ~~~~~~~~~~~~~~~~~~^~~~~~~~
horses.cpp:17:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   17 |         lul1 = 1ll * lul1 * lul1 % modulo;
      |                ~~~~~~~~~~~~~~~~~~^~~~~~~~
horses.cpp: In function 'int solve()':
horses.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i + 1 < candi.size(); i++)
      |                     ~~~~~~^~~~~~~~~~~~~~
horses.cpp:100:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  100 |     ans = ans * lgpow(prd, modulo - 2) % modulo;
      |                       ^~~
horses.cpp:101:12: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  101 |     return ans;
      |            ^~~

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