제출 #316312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
316312		mohamedsobhi777	말 (IOI15_horses)	C++17	100 / 100	1234 ms	43076 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
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;
int X[_N], Y[_N];
set<int> st;
pii tree[_N * 4];
ll a42 = 1ll;
double l42;
int invs[_N];

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 int mul(int x, int y) { return 1ll * x * y % mod; }
int faspow(int x, int y)
{
        if (!y)
                return 1ll;
        int ret = faspow(x, y / 2);
        ret = 1ll * ret * ret % mod;
        if (y & 1)
                ret = 1ll * ret * x % mod;
        return ret;
}
inline int inv(ll x) { return faspow(x, mod - 2); }

void add(int x, ll v, ll old = 1ll)
{
        ++x;
        int nv = mul(v, invs[x - 1]);
        invs[x - 1] = inv(v);
        a42 = mul(a42, nv);
        l42 += log(v) - log(old);
}

int solve()
{
        double mx = 0;
        double lg = 0;
        vector<int> indi;
        int rem = 1ll;
        if (st.size())
        {
                auto it = st.end();
                --it;
                int sz = (int)st.size();
                while (sz--)
                {
                        lg += log(X[(*it)]);
                        int de = (*it);
                        if (de)
                        {
                                rem = mul(rem, invs[*it]);
                                indi.push_back(*it);
                        }
                        if (lg > log(1e9))
                                break;
                        --it;
                }
        }
        double tot = l42 - lg;
        indi.push_back(0);
        rem = mul(rem, inv(X[0]));
        int now = mul(a42, rem);
        int ret = 1ll;
        for (int x = indi.size() - 1; ~x; --x)
        {
                int u = indi[x];
                tot += log(X[u]);
                now = mul(now, X[u]);
                pii gmax = query(0, 1, _N, u + 1, (!x ? n : indi[x - 1] + 1));
                if (tot + log(gmax.first) > mx)
                {
                        ret = mul(now, Y[gmax.second]);
                        mx = tot + log(gmax.first);
                }
        }
        return ret;
}

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;
        for (int i = 0; i < N; ++i)
        {
                invs[i] = 1ll;
                add(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]);
        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();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'int mul(int, int)':
horses.cpp:48:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   48 | inline int mul(int x, int y) { return 1ll * x * y % mod; }
      |                                       ~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int faspow(int, int)':
horses.cpp:54:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   54 |         ret = 1ll * ret * ret % mod;
      |               ~~~~~~~~~~~~~~~~^~~~~
horses.cpp:56:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   56 |                 ret = 1ll * ret * x % mod;
      |                       ~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int inv(ll)':
horses.cpp:59:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   59 | inline int inv(ll x) { return faspow(x, mod - 2); }
      |                                      ^
horses.cpp: In function 'void add(int, ll, ll)':
horses.cpp:64:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   64 |         int nv = mul(v, invs[x - 1]);
      |                      ^
horses.cpp:66:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   66 |         a42 = mul(a42, nv);
      |                   ^~~
horses.cpp: In function 'int solve()':
horses.cpp:98:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   98 |         int now = mul(a42, rem);
      |                       ^~~
horses.cpp:100:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  100 |         for (int x = indi.size() - 1; ~x; --x)
      |                      ~~~~~~~~~~~~^~~

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