Submission #537037

#	Time	Username	Problem	Language	Result	Execution time	Memory
537037		timreizin	Horses (IOI15_horses)	C++17	100 / 100	271 ms	101324 KiB

horses

#include "horses.h"
#include <vector>

using namespace std;

using ll = long long;
using lll = __int128;

const ll MOD = 1e9 + 7;

struct SegTree
{

    int n;
    vector<lll> tree, res;
    vector<ll> moded;

    ll binPow(ll a, ll n)
    {
        ll res = 1;
        while (n)
        {
            if (n & 1) res = (res * a) % MOD;
            a = (a * a) % MOD;
            n >>= 1;
        }
        return res;
    }

    void build(int v, int l, int r, vector<ll> &x, vector<ll> &y)
    {
        if (l > r) return;
        if (l == r)
        {
            tree[v] = x[l];
            res[v] = x[l] * y[l];
            moded[v] = x[l];
            return;
        }
        int m = (l + r) >> 1;
        build(v << 1, l, m, x, y);
        build(v << 1 | 1, m + 1, r, x, y);
        tree[v] = min((lll)1e18 + 1, tree[v << 1] * tree[v << 1 | 1]);
        res[v] = max(res[v << 1], res[v << 1 | 1] * tree[v << 1]);
        moded[v] = moded[v << 1] * moded[v << 1 | 1] % MOD;
    }

    SegTree()
    {}

    SegTree(vector<ll> &x, vector<ll> &y) : n((int)x.size())
    {
        tree.resize(4 * n + 1);
        res.resize(4 * n + 1);
        moded.resize(4 * n + 1);
        build(1, 0, n - 1, x, y);
    }

    void updateX(int p, ll val, int v, int l, int r)
    {
        if (l > r) return;
        if (l == r)
        {
            res[v] = res[v] / tree[v] * val;
            moded[v] = moded[v] * binPow(tree[v], MOD - 2) % MOD * val % MOD;
            tree[v] = val;
            return;
        }
        int m = (l + r) >> 1;
        if (p <= m) updateX(p, val,v << 1, l, m);
        else updateX(p, val,v << 1 | 1, m + 1, r);
        tree[v] = min((lll)1e18 + 1, tree[v << 1] * tree[v << 1 | 1]);
        res[v] = max(res[v << 1], res[v << 1 | 1] * tree[v << 1]);
        moded[v] = moded[v << 1] * moded[v << 1 | 1] % MOD;
    }

    void updateY(int p, ll val, int v, int l, int r)
    {
        if (l > r) return;
        if (l == r)
        {
            res[v] = val * tree[v];
            return;
        }
        int m = (l + r) >> 1;
        if (p <= m) updateY(p, val,v << 1, l, m);
        else updateY(p, val,v << 1 | 1, m + 1, r);
        res[v] = max(res[v << 1], res[v << 1 | 1] * tree[v << 1]);
    }

    ll getModed(int a, int b, int v, int l, int r)
    {
        if (a > r || b < l) return 1;
        if (a == l && b == r) return moded[v];
        int m = (l + r) >> 1;
        return getModed(a, min(b, m), v << 1, l, m) * getModed(max(a, m + 1), b, v << 1 | 1, m + 1, r) % MOD;
    }

    int search(int v, int l, int r, lll mul = 1)
    {
        if (mul * tree[v] < 1e9) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int ret = search(v << 1 | 1, m + 1, r, mul);
        if (ret != -1) return ret;
        return search(v << 1, l, m, mul * tree[v << 1 | 1]);
    }

    pair<lll, lll> get(int a, int b, int v, int l, int r, lll mul = 1)
    {
        if (a > r || b < l) return {0, mul};
        if (a == l && b == r) return {mul * res[v], mul * tree[v]};
        int m = (l + r) >> 1;
        pair<lll, lll> ret1 = get(a, min(b, m), v << 1, l, m, mul);
        pair<lll, lll> ret2 = get(max(a, m + 1), b, v << 1 | 1, m + 1, r, ret1.second);
        return {max(ret1.first, ret2.first), ret2.second};
    }

    int get()
    {
        int ind = max(0, search(1, 0, n - 1));
        ll res = 1;
        if (ind != 0) res = getModed(0, ind - 1, 1, 0, n - 1);
        lll ret = get(ind, n - 1, 1, 0, n - 1).first % MOD;
        return (res * ret) % MOD;
    }

    int update(bool w, int p, ll val)
    {
        if (w) updateY(p, val, 1, 0, n - 1);
        else updateX(p, val, 1, 0, n - 1);
        return get();
    }

};

vector<ll> pref;
SegTree st;

int init(int n, int X[], int Y[])
{
    vector<ll> x(n), y(n);
    for (int i = 0; i < n; ++i)
    {
        x[i] = X[i];
        y[i] = Y[i];
    }
    st = SegTree(x, y);
	return st.get();
}

int updateX(int pos, int val)
{
	return st.update(0, pos, val);
}

int updateY(int pos, int val)
{
	return st.update(1, pos, val);
}

Compilation message (stderr)

horses.cpp: In member function 'll SegTree::binPow(ll, ll)':
horses.cpp:18:24: warning: declaration of 'n' shadows a member of 'SegTree' [-Wshadow]
   18 |     ll binPow(ll a, ll n)
      |                     ~~~^
horses.cpp:14:9: note: shadowed declaration is here
   14 |     int n;
      |         ^
horses.cpp:20:12: warning: declaration of 'res' shadows a member of 'SegTree' [-Wshadow]
   20 |         ll res = 1;
      |            ^~~
horses.cpp:15:23: note: shadowed declaration is here
   15 |     vector<lll> tree, res;
      |                       ^~~
horses.cpp: In member function 'void SegTree::updateX(int, ll, int, int, int)':
horses.cpp:65:58: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type' {aka '__int128'} to 'll' {aka 'long long int'} may change value [-Wconversion]
   65 |             moded[v] = moded[v] * binPow(tree[v], MOD - 2) % MOD * val % MOD;
      |                                                          ^
horses.cpp: In member function 'int SegTree::search(int, int, int, lll)':
horses.cpp:101:17: warning: conversion from 'lll' {aka '__int128'} to 'double' may change value [-Wconversion]
  101 |         if (mul * tree[v] < 1e9) return -1;
horses.cpp: In member function 'int SegTree::get()':
horses.cpp:122:12: warning: declaration of 'res' shadows a member of 'SegTree' [-Wshadow]
  122 |         ll res = 1;
      |            ^~~
horses.cpp:15:23: note: shadowed declaration is here
   15 |     vector<lll> tree, res;
      |                       ^~~
horses.cpp:125:28: warning: conversion from 'lll' {aka '__int128'} to 'int' may change value [-Wconversion]
  125 |         return (res * ret) % MOD;
      |                ~~~~~~~~~~~~^~~~~

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