Submission #825212

#	Time	Username	Problem	Language	Result	Execution time	Memory
825212		Nelt	Horses (IOI15_horses)	C++17	100 / 100	249 ms	60820 KiB

horses

#include "horses.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define ANDROID                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define elif else if
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define pb push_back
#define logi(a) __lg(a)
#define sqrt(a) sqrtl(a)
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 5e5 + 5, mod = 1e9 + 7;
ll a[N], b[N], n;
ll t[N];
ll binpow(ll n, ll p)
{
    ll ans = 1;
    n %= mod;
    while (p)
    {
        ans = (p & 1 ? (ans * n) % mod : ans);
        n = (n * n) % mod;
        p >>= 1;
    }
    return ans;
}
ll inv(ll x)
{
    return binpow(x, mod - 2);
}
ll product(ll i)
{
    ll res = 1;
    for (; i > 0; i = (i & (i + 1)) - 1)
        res = res * t[i] % mod;
    return res;
}
void upd(ll i, ll d)
{
    for (; i <= n; i = (i | (i + 1)))
        t[i] = t[i] * d % mod;
}
struct SegTree
{
    ll n;
    vv(ll) st;
    SegTree(ll sz = 0, bool input = false)
    {
        n = sz;
        st.resize((n + 1) << 1, 0);
    }
    void set(ll i, ll val)
    {
        st[i + n - 1] = val;
    }
    void build()
    {
        for (ll i = n - 1; i >= 1; i--)
            st[i] = max(st[i << 1], st[i << 1 | 1]);
    }
    void modify(ll p, ll val)
    {
        for (st[p += n - 1] = val; p > 1; p >>= 1)
            st[p >> 1] = max(st[p], st[p ^ 1]);
    }
    ll query(ll l, ll r)
    {
        ll ans = 0;
        for (l += n - 1, r += n; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1)
                ans = max(ans, st[l++]);
            if (r & 1)
                ans = max(ans, st[--r]);
        }
        return ans;
    }
} st(N);
ss(ll) s;
ll solve()
{
    __int128 prod = 1;
    auto it = --s.end();
    while (it != s.begin() and prod * a[*it] <= 1e9)
        prod *= a[*it], it--;
    // cout << s.size() << endl;
    if (prod * a[*it] <= 1e9)
    {
        __int128 ans = st.query(1, n), one = 1;
        for (; *it != n + 1; it++)
            ans = max(ans, one * product(*it) * st.query(*it, n));
        return ans % mod;
    }
    prod = 1;
    __int128 ans = 1, start = *it;
    for (; *it != n + 1; it++)
        prod *= a[*it], ans = max(ans, prod * st.query(*it, n));
    return ans % mod * product(start - 1) % mod;
}
int init(int N, int X[], int Y[])
{
    n = N;
    for (ll i = 0; i < n; i++)
        a[i + 1] = X[i], b[i + 1] = Y[i], t[i + 1] = 1;
    for (ll i = 1; i <= n; i++)
    {
        if (a[i] > 1)
            s.ins(i);
        st.set(i, b[i]);
        upd(i, a[i]);
    }
    st.build();
    a[n + 1] = b[n + 1] = 1;
    s.ins(n + 1);
    return solve();
}

int updateX(int pos, int val)
{
    pos++;
    upd(pos, inv(a[pos]) * val % mod);
    a[pos] = val;
    if (a[pos] > 1)
        s.ins(pos);
    elif (s.count(pos))
        s.erase(pos);
    return solve();
}
int updateY(int pos, int val)
{
    pos++;
    st.modify(pos, b[pos] = val);
    return solve();
}

Compilation message (stderr)

horses.cpp: In function 'long long int binpow(long long int, long long int)':
horses.cpp:48:14: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   48 | ll binpow(ll n, ll p)
      |              ^
horses.cpp:46:16: note: shadowed declaration is here
   46 | ll a[N], b[N], n;
      |                ^
horses.cpp: In constructor 'SegTree::SegTree(long long int, bool)':
horses.cpp:80:29: warning: unused parameter 'input' [-Wunused-parameter]
   80 |     SegTree(ll sz = 0, bool input = false)
      |                        ~~~~~^~~~~~~~~~~~~
horses.cpp: In function 'long long int solve()':
horses.cpp:117:37: warning: conversion from '__int128' to 'double' may change value [-Wconversion]
  117 |     while (it != s.begin() and prod * a[*it] <= 1e9)
      |                                ~~~~~^~~~~~~~
horses.cpp:120:14: warning: conversion from '__int128' to 'double' may change value [-Wconversion]
  120 |     if (prod * a[*it] <= 1e9)
      |         ~~~~~^~~~~~~~
horses.cpp:125:20: warning: conversion from '__int128' to 'long long int' may change value [-Wconversion]
  125 |         return ans % mod;
      |                ~~~~^~~~~
horses.cpp:131:38: warning: conversion from '__int128' to 'long long int' may change value [-Wconversion]
  131 |     return ans % mod * product(start - 1) % mod;
      |                                ~~~~~~^~~
horses.cpp:131:43: warning: conversion from '__int128' to 'long long int' may change value [-Wconversion]
  131 |     return ans % mod * product(start - 1) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:133:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  133 | int init(int N, int X[], int Y[])
      |          ~~~~^
horses.cpp:45:10: note: shadowed declaration is here
   45 | const ll N = 5e5 + 5, mod = 1e9 + 7;
      |          ^
horses.cpp:148:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  148 |     return solve();
      |            ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:160:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  160 |     return solve();
      |            ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:166:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  166 |     return solve();
      |            ~~~~~^~

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