Submission #246582

#	Time	Username	Problem	Language	Result	Execution time	Memory
246582		Artyom123	Horses (IOI15_horses)	C++14	100 / 100	549 ms	70212 KiB

horses

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define ll long long
#define ld long double

const int INF = 2e9 + 1;
const ll INFLL = 1e18 + 1;
const int mod = 1e9 + 7;
const int MAXN = 5e5 + 5;

ll x[MAXN], y[MAXN];

vector<int> t;

void build(int v, int vl, int vr, vector<ll> &a) {
    if (vr - vl == 1) {
        t[v] = a[vl];
        return;
    }
    int vm = (vl + vr) / 2;
    build(2 * v + 1, vl, vm, a);
    build(2 * v + 2, vm, vr, a);
    t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}

void modify(int v, int vl, int vr, int ind, int val) {
    if (vr - vl == 1) {
        t[v] = val;
        return;
    }
    int vm = (vl + vr) / 2;
    if (ind < vm) modify(2 * v + 1, vl, vm, ind, val);
    else modify(2 * v + 2, vm, vr, ind, val);
    t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}

int get(int v, int vl, int vr, int l, int r) {
    if (r <= vl || l >= vr) return 0;
    if (vl >= l && vr <= r) return t[v];
    int vm = (vl + vr) / 2;
    return max(get(2 * v + 1, vl, vm, l, r),
               get(2 * v + 2, vm, vr, l, r));
}

struct segment{
    int l, r, mx;
    segment(){}
    segment(int l, int r, int mx) : l(l), r(r), mx(mx) {}
    bool operator< (const segment &a) const {
        return l < a.l;
    }
};

ll total = 1;

ll my_pow(ll n, ll m) {
    if (m == 0) return 1;
    ll now = my_pow(n, m / 2);
    if (m % 2 == 0) return (now * now) % mod;
    return (((now * now) % mod) * n) % mod;
}

set<segment> s;

int solve() {
    auto it = s.end();
    int ind = -1;
    ll now = 1;
    ll suff = 1;
    assert(s.size());
    for (int i = 0; i < 70 && it != s.begin(); i++) {
        it--;
        ll x1 = x[it->l], y1 = it->mx;
        if (y1 >= now) {
            ind = i;
        }
        if (x1 * y1 > 1e9) {
            break;
        }
        if (now * x1 > 1e9) {
            break;
        }
        now = max(now * x1, x1 * y1);
    }
    ll ans = 0;
    it = s.end();
    for (int i = 0; ; i++) {
        it--;
        if (i == ind) {
            ans = (total * my_pow(suff, mod - 2)) % mod;
            ans *= it->mx;
            ans %= mod;
            break;
        }
        suff *= x[it->l];
        suff %= mod;
    }
    return ans;
}

int n;

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];
    t.resize(4 * n);
    vector<ll> a(n);
    for (int i = 0; i < n; i++) a[i] = Y[i];
    build(0, 0, n, a);
    vector<pair<int, int>> seg;
    for (int i = 0; i < n; i++) {
        total *= x[i];
        total %= mod;
        if (x[i] >= 2) {
            seg.pb(i, i);
            continue;
        }
        if (i != 0 && x[i] == x[i - 1]) {
            seg.back().se++;
            continue;
        }
        seg.pb(i, i);
    }
    for (auto &c : seg) {
        assert(get(0, 0, n, c.fi, c.se + 1) >= 1);
        s.insert(segment(c.fi, c.se, get(0, 0, n, c.fi, c.se + 1)));
    }
    return solve();
}

int updateX(int pos, int val) {
    total *= my_pow(x[pos], mod - 2);
    total %= mod;
    total *= val;
    total %= mod;
    segment lol(pos, pos, 0);
    auto it = s.upper_bound(lol);
    it--;
    if (x[pos] == val) return solve();
    if (x[pos] > 1 && val > 1) {
        x[pos] = val;
        return solve();
    }
    if (x[pos] == 1 && val > 1) {
        x[pos] = val;
        segment now = *it;
        int l = now.l, r = now.r;
        if (now.l == now.r) {
            return solve();
        }
        if (pos == now.l) {
            s.erase(it);
            assert(get(0, 0, n, pos, pos + 1) >= 1 && get(0, 0, n, l + 1, r + 1) >= 1);
            s.insert(segment(pos, pos, get(0, 0, n, pos, pos + 1)));
            s.insert(segment(l + 1, r, get(0, 0, n, l + 1, r + 1)));
            return solve();
        }
        if (pos == now.r) {
            s.erase(it);
            assert(get(0, 0, n, pos, pos + 1) >= 1 && get(0, 0, n, l, r) >= 1);
            s.insert(segment(pos, pos, get(0, 0, n, pos, pos + 1)));
            s.insert(segment(l, r - 1, get(0, 0, n, l, r)));
            return solve();
        }
        s.erase(it);
        assert(get(0, 0, n, l, pos) >= 1 && get(0, 0, n, pos, pos + 1) >= 1 && get(0, 0, n, pos + 1, r + 1) >= 1);
        s.insert(segment(l, pos - 1, get(0, 0, n, l, pos)));
        s.insert(segment(pos, pos, get(0, 0, n, pos, pos + 1)));
        s.insert(segment(pos + 1, r, get(0, 0, n, pos + 1, r + 1)));
        return solve();
    }
    if (x[pos] > 1 && val == 1) {
        x[pos] = val;
        segment now = *it;
        int l = now.l, r = now.r;
        segment now1(-1, -1, -1), now2(-1, -1, -1);
        if (now.l != 0 && x[now.l - 1] == 1) {
            it--;
            l = it->l;
            now1 = *it;
            it++;
        }
        if (now.r != n - 1 && x[now.r + 1] == 1) {
            it++;
            r = it->r;
            now2 = *it;
            it--;
        }
        s.erase(now);
        s.erase(now1);
        s.erase(now2);
        now.l = l, now.r = r;
        now.mx = get(0, 0, n, l, r + 1);
        assert(now.mx >= 1);
        s.insert(now);
    }
    return solve();
}

int updateY(int pos, int val) {
    modify(0, 0, n, pos, val);
    segment lol(pos, pos, 0);
    auto it = s.upper_bound(lol);
    it--;
    segment now = *it;
    s.erase(it);
    now.mx = get(0, 0, n, now.l, now.r + 1);
    assert(now.mx >= 1);
    s.insert(now);
    return solve();
}

Compilation message (stderr)

horses.cpp: In function 'void build(int, int, int, std::vector<long long int>&)':
horses.cpp:23:20: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' may alter its value [-Wconversion]
         t[v] = a[vl];
                    ^
horses.cpp: In constructor 'segment::segment(int, int, int)':
horses.cpp:54:35: warning: declaration of 'mx' shadows a member of 'segment' [-Wshadow]
     segment(int l, int r, int mx) : l(l), r(r), mx(mx) {}
                                   ^
horses.cpp:52:15: note: shadowed declaration is here
     int l, r, mx;
               ^~
horses.cpp:54:35: warning: declaration of 'r' shadows a member of 'segment' [-Wshadow]
     segment(int l, int r, int mx) : l(l), r(r), mx(mx) {}
                                   ^
horses.cpp:52:12: note: shadowed declaration is here
     int l, r, mx;
            ^
horses.cpp:54:35: warning: declaration of 'l' shadows a member of 'segment' [-Wshadow]
     segment(int l, int r, int mx) : l(l), r(r), mx(mx) {}
                                   ^
horses.cpp:52:9: note: shadowed declaration is here
     int l, r, mx;
         ^
horses.cpp: In function 'int solve()':
horses.cpp:83:16: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
         if (x1 * y1 > 1e9) {
             ~~~^~~~
horses.cpp:86:17: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
         if (now * x1 > 1e9) {
             ~~~~^~~~
horses.cpp:104:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ans;
            ^~~

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