Submission #316268

#	Time	Username	Problem	Language	Result	Execution time	Memory
316268		mohamedsobhi777	Horses (IOI15_horses)	C++14	34 / 100	1592 ms	38632 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#pragma GCC optimize("trapv")

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

const int _N = 5e5 + 7, mod = 1e9 + 7;
const ll inf = 2e18;
int n, m;
ll X[_N], Y[_N];
ll bit[_N];
double bit2[_N];
set<int> st;
pii tree[_N * 4];

void update(int node, int L, int R, int ix, int val)
{
        if (L == R)
        {
                tree[node] = {val, ix - 1};
                return;
        }

        int mid = (L + R) >> 1;
        if (ix <= mid)
                update(node * 2 + 1, L, mid, ix, val);
        else
                update(node * 2 + 2, mid + 1, R, ix, val);
        tree[node] = max(tree[node * 2 + 1], tree[node * 2 + 2]);
}

pii query(int node, int L, int R, int l, int r)
{
        if (l > r || l > R || r < L)
                return {-1, -1};
        if (L >= l && R <= r)
                return tree[node];
        int mid = (L + R) >> 1;
        pii s1 = query(node * 2 + 1, L, mid, l, r);
        pii s2 = query(node * 2 + 2, mid + 1, R, l, r);
        return max(s1, s2);
}

inline ll mul(ll x, ll y) { return 1ll * (x % mod) * (y % mod) % mod; }
ll faspow(ll x, ll y)
{
        if (!y)
                return 1ll;
        ll ret = faspow(x, y / 2);
        ret = 1ll * ret * ret % mod;
        if (y & 1)
                ret = 1ll * ret * x % mod;
        return ret;
}
inline ll inv(ll x) { return faspow(x, mod - 2); }
inline ll add(ll x, ll y) { return (x + y >= mod ? x + y - mod : x + y); }

void add(int x, ll v, ll old = 1ll)
{
        ++x;
        for (; x < _N; x += x & -x)
                bit[x] = mul(bit[x], mul(v, inv(old)));
}

ll eval(int x)
{
        ++x;
        ll ret = 1ll;
        for (; x; x -= x & -x)
                ret = 1ll * ret * bit[x] % mod;
        return ret;
}

void add2(int pos, double v)
{
        ++pos;
        for (; pos < _N; pos += pos & -pos)
                bit2[pos] += v;
}

double get2(int pos)
{
        ++pos;
        double ret = 0;
        for (; pos; pos -= pos & -pos)
                ret += bit2[pos];
        return ret;
}

ll solve()
{
        double tot = 0;
        double mx = 0;
        int k = 0;
        int de = n - 1;
        double lg = 0;
        vector<int> indi = {0};
        if (st.size())
        {
                auto it = st.end();
                --it;
                int sz = (int)st.size();
                while (sz--)
                {
                        lg += log(X[(*it)]);
                        de = (*it);
                        assert(X[*it] > 1);
                        if (de)
                                indi.push_back(*it);
                        if (lg > log(1e9))
                                break;
                        --it;
                }
                if (lg <= log(1e9))
                        de = 0;
        }
        else
        {
                de = 0;
        }
        sort(indi.begin(), indi.end());
        tot = get2(de - 1);
        for (auto u : indi)
        {
                tot += log(X[u]);
                pii gmax = query(0, 1, _N, u + 1, n);
                if (tot + log(gmax.first) > mx)
                {
                        mx = tot + log(gmax.first);
                        k = gmax.second;
                }
        }
        return mul(eval(k), Y[k]);
}

void putit(int x, int val)
{
        if (val > 1)
                st.insert(x);
        else
        {
                st.erase(x);
        }
}

int init(int N, int _X[], int _Y[])
{
        n = N;
        fill(bit, bit + _N, 1);
        for (int i = 0; i < N; ++i)
        {
                add(i, _X[i]);
                add2(i, _X[i]);
                putit(i, _X[i]);
                update(0, 1, _N, i + 1, _Y[i]);
                X[i] = _X[i];
                Y[i] = _Y[i];
        }
        return solve();
}

int updateX(int pos, int val)
{
        add(pos, val, X[pos]);
        add2(pos, log(val) - log(X[pos]));
        putit(pos, val);
        X[pos] = val;
        return solve();
}

int updateY(int pos, int val)
{
        Y[pos] = val;
        update(0, 1, _N, pos + 1, val);
        return solve();
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:162:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  162 |         return solve();
      |                ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:171:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  171 |         return solve();
      |                ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:178:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  178 |         return solve();
      |                ~~~~~^~

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