제출 #536998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536998		timreizin	말 (IOI15_horses)	C++17	17 / 100	139 ms	90200 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;

    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;
            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]);
    }

    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);
        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]);
    }

    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 r;
        return search(v << 1, l, m, mul * tree[v << 1 | 1]);
    }

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

    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) % 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);
}

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

horses.cpp: In member function 'int SegTree::search(int, int, int, lll)':
horses.cpp:88:17: warning: conversion from 'lll' {aka '__int128'} to 'double' may change value [-Wconversion]
   88 |         if (mul * tree[v] < 1e9) return -1;
horses.cpp: In member function 'int SegTree::get()':
horses.cpp:107:12: warning: declaration of 'res' shadows a member of 'SegTree' [-Wshadow]
  107 |         ll res = 1;
      |            ^~~
horses.cpp:15:23: note: shadowed declaration is here
   15 |     vector<lll> tree, res;
      |                       ^~~
horses.cpp:110:28: warning: conversion from 'lll' {aka '__int128'} to 'int' may change value [-Wconversion]
  110 |         return (res * ret) % MOD;
      |                ~~~~~~~~~~~~^~~~~

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