Submission #341047

#	Time	Username	Problem	Language	Result	Execution time	Memory
341047		12tqian	Horses (IOI15_horses)	C++17	100 / 100	1025 ms	49772 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
template <int MOD, int RT> struct Mint {
    static const int mod = MOD;
    static constexpr Mint rt() { return RT; } // primitive root for FFT
    int v; 
    explicit operator int() const { return v; } // explicit -> don't silently convert to int
    Mint() { v = 0; }
    Mint(long long _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; }
    friend bool operator == (const Mint& a, const Mint& b) { return a.v == b.v; }
    friend bool operator != (const Mint& a, const Mint& b) { return !(a == b); }
    friend bool operator < (const Mint& a, const Mint& b) { return a.v < b.v; }
    friend bool operator > (const Mint& a, const Mint& b) { return a.v > b.v; }
    friend bool operator <= (const Mint& a, const Mint& b) { return a.v <= b.v; }
    friend bool operator >= (const Mint& a, const Mint& b) { return a.v >= b.v; }
    friend std::istream& operator >> (std::istream& in, Mint& a) { 
        long long x; std::cin >> x; a = Mint(x); return in; }
    friend std::ostream& operator << (std::ostream& os, const Mint& a) { return os << a.v; }
    Mint& operator += (const Mint& m) { 
        if ((v += m.v) >= MOD) v -= MOD; 
        return *this; }
    Mint& operator -= (const Mint& m) { 
        if ((v -= m.v) < 0) v += MOD; 
        return *this; }
    Mint& operator *= (const Mint& m) { 
        v = (long long ) v * m.v % MOD; return *this; }
    Mint& operator /= (const Mint& m) { return (*this) *= inv(m); }
    friend Mint pow(Mint a, long long p) {
        Mint ans = 1; assert(p >= 0);
        for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
        return ans; 
    }
    friend Mint inv(const Mint& a) { assert(a.v != 0); return pow(a, MOD - 2); }
    Mint operator - () const { return Mint(-v); }
    Mint& operator ++ () { return *this += 1; }
    Mint& operator -- () { return *this -= 1; }
    friend Mint operator + (Mint a, const Mint& b) { return a += b; }
    friend Mint operator - (Mint a, const Mint& b) { return a -= b; }
    friend Mint operator * (Mint a, const Mint& b) { return a *= b; }
    friend Mint operator / (Mint a, const Mint& b) { return a /= b; }
};
 
using mi = Mint<MOD, 5>;
typedef double db;
 
template <class T> struct LazySeg {
    std::vector<T> mn, lazy;
    vector<int> id;
    int sz;
    void init(int sz_) {
        sz = 1;
        while (sz < sz_) sz *= 2;
        mn.assign(2 * sz, 0);
        lazy.assign(2 * sz, 0);
        id.assign(2 * sz, 0);
        for (int i = 0; i < sz; i++)
            id[i + sz] = i;
        build();
    }
    void push(int ind, int L, int R) {
        mn[ind] += lazy[ind];
        if (L != R) {
            lazy[2 * ind] += lazy[ind];
            lazy[2 * ind + 1] += lazy[ind];
        }
        lazy[ind] = 0;
    }
    void pull(int ind) {
        if (mn[2 * ind] >= mn[2 * ind + 1]) {
            mn[ind] = mn[2 * ind];
            id[ind] = id[2 * ind];
        } else {
            mn[ind] = mn[2 *ind + 1];
            id[ind] = id[2 * ind + 1];
        }
 
    }
    void build() {
        for (int i = sz - 1; i >= 1; i--) {
            pull(i);
        }
    }
    void upd(int lo, int hi, T inc, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (hi < L || R < lo) return;
        if (lo <= L && R <= hi) {
            lazy[ind] = inc;
            push(ind, L, R);
            return;
        }
        int M = (L + R) / 2;
        upd(lo, hi, inc, 2 * ind, L, M);
        upd(lo, hi, inc, 2 * ind + 1, M + 1, R);
        pull(ind);
    }
    pair<T, int> qmin(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (lo > R || L > hi) return {0, id[ind]};
        if (lo <= L && R <= hi) return {mn[ind], id[ind]};
        int M = (L + R) / 2;
        return max(qmin(lo, hi, 2 * ind, L, M), qmin(lo, hi, 2 * ind + 1, M + 1, R));
    }
};
template <class T> struct LazySegProd {
    std::vector<T> mn, lazy;
    int sz;
    void init(int sz_) {
        sz = 1;
        while (sz < sz_) sz *= 2;
        mn.assign(2 * sz, 1);
        lazy.assign(2 * sz, 1);
    }
    void push(int ind, int L, int R) {
        mn[ind] *= lazy[ind];
        if (L != R) {
            lazy[2 * ind] *= lazy[ind];
            lazy[2 * ind + 1] *= lazy[ind];
        }
        lazy[ind] = 1;
    }
    void upd(int lo, int hi, T inc, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (hi < L || R < lo) return;
        if (lo <= L && R <= hi) {
            lazy[ind] = inc;
            push(ind, L, R);
            return;
        }
        int M = (L + R) / 2;
        upd(lo, hi, inc, 2 * ind, L, M);
        upd(lo, hi, inc, 2 * ind + 1, M + 1, R);
    }
    T qmin(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (lo > R || L > hi) return MOD - 1;
        if (lo <= L && R <= hi) return mn[ind];
        int M = (L + R) / 2;
        return min(qmin(lo, hi, 2 * ind, L, M), qmin(lo, hi, 2 * ind + 1, M + 1, R));
    }
};
 
 
int n;
LazySegProd<mi> seg_compute;
LazySeg<db> seg;
vector<int> x, y;
mi ask() {
    int id = seg.qmin(0, n-1).second;
    return seg_compute.qmin(id, id);
}
int init(int N, int X[], int Y[]) {
    n = N;
    seg_compute.init(n);
    seg.init(n);
    x.reserve(n), y.reserve(n);
    mi run = 1;
    db sum = 0;
    for (int i = 0; i < n; i++) {
        x[i] = X[i], y[i] = Y[i];
        run *= x[i];
        sum += log2(x[i]);
        seg_compute.upd(i, i, run * y[i]);
        seg.upd(i, i, sum + log2(y[i]));
    }
    return ask().v;
}
 
int updateX(int pos, int val) { 
    db diff = log2(val) - log2(x[pos]);
    mi change = val / mi(x[pos]);
    seg.upd(pos, n-1, diff);
    seg_compute.upd(pos, n-1, change);
    x[pos] = val;
    return ask().v;
}
 
int updateY(int pos, int val) {
    db diff = log2(val) - log2(y[pos]);
    mi change = val / mi(y[pos]);
    seg.upd(pos, pos, diff);
    seg_compute.upd(pos, pos, change);
    y[pos] = val;
    return ask().v;
}

Compilation message (stderr)

horses.cpp: In instantiation of 'Mint<MOD, RT>& Mint<MOD, RT>::operator*=(const Mint<MOD, RT>&) [with int MOD = 1000000007; int RT = 5]':
horses.cpp:167:19:   required from here
horses.cpp:29:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   29 |         v = (long long ) v * m.v % MOD; return *this; }
      |             ~~~~~~~~~~~~~~~~~~~~~^~~~~

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