Submission #403148

#	Time	Username	Problem	Language	Result	Execution time	Memory
403148		ruadhan	Horses (IOI15_horses)	C++17	17 / 100	298 ms	48088 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
typedef long long ll;
#define sz(x) (int)x.size()
using namespace std;

const int MOD = 1e9 + 7;
const int MX = 5e5 + 5;
int N;
ll X[MX], Y[MX];

struct ModVal
{
    ll div = 0, mod = 0;
    ModVal(ll _div, ll _mod)
    {
        div = _div;
        mod = _mod;
    }
    bool operator<(const ModVal &other) const
    {
        if (div == other.div)
            return mod < other.mod;
        return div < other.div;
    }
    ModVal operator*(const ModVal &other)
    {
        ModVal ret(0, 0);
        ret.div = div * other.div;
        ret.mod = (mod * other.mod) % MOD;
        ret.div += ((mod * other.mod) / MOD) % MOD;
        return ret;
    }
    ModVal operator*(const ll &integer)
    {
        ModVal ret(0, 0);
        ret.div = div + ((mod * integer) / MOD);
        ret.mod = (mod * integer) % MOD;
        return ret;
    }
};

template <class T>
struct SegMax
{
    const T ID = {0, 0};
    T comb(T a, T b) { return max(a, b); }
    int n;
    vector<T> seg;
    void init(int _n)
    {
        n = _n;
        seg.assign(2 * n, ID);
    }
    void pull(int p)
    {
        seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
    }
    void upd(int p, T val)
    {
        seg[p += n] = val;
        for (p /= 2; p; p /= 2)
            pull(p);
    }
    T query(int l, int r)
    {
        T ra = ID, rb = ID;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2)
        {
            if (l & 1)
                ra = comb(ra, seg[l++]);
            if (r & 1)
                rb = comb(seg[--r], rb);
        }
        return comb(ra, rb);
    }
};

SegMax<ModVal> mx;

template <class T>
struct SegMul
{
    const T ID = {0, 1};
    T comb(T a, T b) { return (a * b); }
    int n;
    vector<T> seg;
    void init(int _n)
    {
        n = _n;
        seg.assign(2 * n, ID);
    }
    void pull(int p)
    {
        seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
    }
    void upd(int p, T val)
    {
        int pos = p;
        seg[p += n] = val;
        for (p /= 2; p; p /= 2)
            pull(p);
        mx.upd(pos, query(1, pos) * Y[pos - 1]);
    }
    T query(int l, int r)
    {
        T ra = ID, rb = ID;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2)
        {
            if (l & 1)
                ra = comb(ra, seg[l++]);
            if (r & 1)
                rb = comb(seg[--r], rb);
        }
        return comb(ra, rb);
    }
};

SegMul<ModVal> mul;

// int init(int N, vector<int> X, vector<int> Y)
int init(int N, int X[], int Y[])
{
    ::N = N;
    for (int i = 0; i < N; i++)
        ::X[i] = X[i];
    for (int i = 0; i < N; i++)
        ::Y[i] = Y[i];
    mx.init(N + 1), mul.init(N + 1);
    for (int i = 1; i <= N; i++)
        mul.upd(i, ModVal(0, X[i - 1]));
    return mx.query(1, N).mod;
}

int updateX(int pos, int val)
{
    X[pos - 1] = val;
    mul.upd(pos, ModVal(0, val));
    return mx.query(1, N).mod;
}

int updateY(int pos, int val)
{
    Y[pos - 1] = val;
    mx.upd(pos, mul.query(1, pos) * Y[pos - 1]);
    return mx.query(1, N).mod;
}

// int main()
// {
//     int n, m;
//     cin >> n >> m;
//     vector<int> a1(n), a2(n);
//     for (auto &x : a1)
//         cin >> x;
//     for (auto &x : a2)
//         cin >> x;
//     cout << init(n, a1, a2) << '\n';
//     // for (auto x : mx.seg)
//     //     cout << x.mod << " ";
//     // cout << '\n';
//     // for (auto x : mul.seg)
//     //     cout << x.mod << " ";
//     // cout << '\n';
//     while (m--)
//     {
//         int a, b, c;
//         cin >> a >> b >> c;
//         b++;
//         if (a == 1)
//         {
//             cout << updateX(b, c) << '\n';
//         }
//         else
//         {
//             cout << updateY(b, c) << '\n';
//         }
//     }
//     // for (auto x : mx.seg)
//     //     cout << x.mod << " ";
//     // cout << '\n';
//     // for (auto x : mul.seg)
//     //     cout << x.mod << " ";
//     // cout << '\n';
//     // cout << mul.query(1, 2).mod << '\n';
//     return 0;
// }

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:122:30: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
  122 | int init(int N, int X[], int Y[])
      |                          ~~~~^~~
horses.cpp:10:11: note: shadowed declaration is here
   10 | ll X[MX], Y[MX];
      |           ^
horses.cpp:122:21: warning: declaration of 'X' shadows a global declaration [-Wshadow]
  122 | int init(int N, int X[], int Y[])
      |                 ~~~~^~~
horses.cpp:10:4: note: shadowed declaration is here
   10 | ll X[MX], Y[MX];
      |    ^
horses.cpp:122:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  122 | int init(int N, int X[], int Y[])
      |          ~~~~^
horses.cpp:9:5: note: shadowed declaration is here
    9 | int N;
      |     ^
horses.cpp:132:27: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  132 |     return mx.query(1, N).mod;
      |            ~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:139:27: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  139 |     return mx.query(1, N).mod;
      |            ~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:146:27: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  146 |     return mx.query(1, N).mod;
      |            ~~~~~~~~~~~~~~~^~~

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