Submission #368366

#	Time	Username	Problem	Language	Result	Execution time	Memory
368366		KoD	Horses (IOI15_horses)	C++17	100 / 100	554 ms	57068 KiB

horses

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <set>

#ifndef LOCAL
#include "horses.h"
#endif

namespace Solver {
    template <class T>
    using Vec = std::vector<T>;
    using ll = long long;

    constexpr ll MOD = 1000000007;

    ll mod_pow(ll x, ll e) {
        ll ret = 1;
        while (e > 0) {
            if (e & 1) {
                ret *= x;
                ret %= MOD;
            }
            x *= x;
            x %= MOD;
            e >>= 1;
        }
        return ret;
    }

    ll mod_inv(ll x) {
        return mod_pow(x, MOD - 2);
    }

    template <class Monoid>
    struct Segtree { 
        Vec<Monoid> data;
        Segtree() = default;
        Segtree(const int n): data(2 * n, Monoid::zero()) { }
        void fetch(const int k) {
            data[k] = data[k * 2] + data[k * 2 + 1];
        }
        void assign(int i, const Monoid &mn) {
            i += size();
            data[i] = mn;
            while (i > 1) {
                i >>=  1;
                fetch(i);
            }
        }
        Monoid fold(int l, int r) {
            l += size();
            r += size();
            auto sumL = Monoid::zero();
            auto sumR = Monoid::zero();
            while (l < r) {
                if (l & 1) {
                    sumL = sumL + data[l];
                    l += 1;
                }
                if (r & 1) {
                    r -= 1;
                    sumR = data[r] + sumR;
                }
                l >>= 1;
                r >>= 1;
            }
            return sumL + sumR;
        }
        int size() const {
            return (int) data.size() / 2;
        }
    };

    struct Prod {
        static Prod zero() { return Prod { 1 }; }
        ll value;
        Prod operator + (const Prod &other) const {
            ll tmp = value * other.value;
            return Prod { tmp >= MOD ? 0 : tmp };
        }
    };

    struct Max {
        static Max zero() { return Max { 0 }; }
        ll value;
        Max operator + (const Max &other) const {
            return Max { std::max(value, other.value) };
        }
    };

    ll all_prod = 1;
    Segtree<Prod> x_prod;
    Segtree<Max> y_max;
    std::set<int> consider;

    void setx(const int i, const int x) {
        all_prod *= mod_inv(x_prod.fold(i, i + 1).value);
        all_prod %= MOD;
        all_prod *= x;
        all_prod %= MOD;
        x_prod.assign(i, Prod { x });
        if (x == 1) {
            if (i != 0 && i + 1 != (int) x_prod.size()) {
                consider.erase(i);
            }
        }
        if (x >= 2) {
            consider.insert(i);
        }
    }

    void sety(const int i, const int y) {
        y_max.assign(i, Max { y });
    }

    ll fold() {
        ll up = 0, down = 1;
        int last = x_prod.size();
        for (auto itr = consider.rbegin(); itr != consider.rend(); ++itr) {
            const auto i = *itr;
            const auto x = x_prod.fold(i + 1, x_prod.size()).value;
            if (x == 0) {
                break;
            }
            const auto y = y_max.fold(i, last).value;
            if (up * x < down * y) { 
                up = y;
                down = x;
            }
            last = i;
        }
        return (((all_prod * mod_inv(down)) % MOD) * up) % MOD;
    }
}

int init(int N, int X[], int Y[]) {
    using namespace Solver;
    x_prod = Segtree<Prod>(N);
    y_max = Segtree<Max>(N);
    consider.insert(0);
    consider.insert(N - 1);
    for (int i = 0; i < N; ++i) {
        setx(i, X[i]);
        sety(i, Y[i]);
    }
    return fold();
}

int updateX(int pos, int val) {
    using namespace Solver;
    setx(pos, val);
    return fold();
}

int updateY(int pos, int val) {
    using namespace Solver;
    sety(pos, val);
    return fold();
}

#ifdef LOCAL
int main() {
    int N;
    int X[100] = {};
    int Y[100] = {};
    std::cin >> N;
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i];
    }
    for (int i = 0; i < N; ++i) {
        std::cin >> Y[i];
    }
    std::cout << init(N, X, Y) << '\n';
    int M;
    std::cin >> M;
    while (M--) {
        int t, p, v;
        std::cin >> t >> p >> v;
        if (t == 1) {
            std::cout << updateX(p, v) << '\n';
        }
        else {
            std::cout << updateY(p, v) << '\n';
        }
    }
    return 0;
}
#endif

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:149:16: warning: conversion from 'Solver::ll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  149 |     return fold();
      |            ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:155:16: warning: conversion from 'Solver::ll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  155 |     return fold();
      |            ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:161:16: warning: conversion from 'Solver::ll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  161 |     return fold();
      |            ~~~~^~

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