oj.uz

Submission #246582

# Submission time Handle Problem Language Result Execution time Memory
246582 2020-07-09T16:00:40 Z Artyom123 Horses (IOI15_horses) C++14
100 / 100
 549 ms 70212 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 5 ms 436 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 5 ms 256 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 6 ms 512 KB Output is correct
24 Correct 6 ms 512 KB Output is correct
25 Correct 6 ms 512 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Correct 6 ms 384 KB Output is correct
28 Correct 6 ms 512 KB Output is correct
29 Correct 6 ms 384 KB Output is correct
30 Correct 6 ms 512 KB Output is correct
31 Correct 6 ms 384 KB Output is correct
32 Correct 6 ms 384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 59116 KB Output is correct
2 Correct 539 ms 69988 KB Output is correct
3 Correct 487 ms 61152 KB Output is correct
4 Correct 483 ms 65120 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 6 ms 512 KB Output is correct
25 Correct 6 ms 512 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Correct 6 ms 512 KB Output is correct
28 Correct 6 ms 512 KB Output is correct
29 Correct 6 ms 384 KB Output is correct
30 Correct 6 ms 512 KB Output is correct
31 Correct 6 ms 384 KB Output is correct
32 Correct 7 ms 384 KB Output is correct
33 Correct 64 ms 27776 KB Output is correct
34 Correct 63 ms 27768 KB Output is correct
35 Correct 306 ms 69984 KB Output is correct
36 Correct 297 ms 69860 KB Output is correct
37 Correct 58 ms 25856 KB Output is correct
38 Correct 283 ms 62048 KB Output is correct
39 Correct 48 ms 25856 KB Output is correct
40 Correct 285 ms 64992 KB Output is correct
41 Correct 47 ms 25856 KB Output is correct
42 Correct 54 ms 25856 KB Output is correct
43 Correct 275 ms 65376 KB Output is correct
44 Correct 277 ms 65376 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 360 KB Output is correct
4 Correct 5 ms 304 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 6 ms 512 KB Output is correct
25 Correct 6 ms 512 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Correct 6 ms 384 KB Output is correct
28 Correct 6 ms 512 KB Output is correct
29 Correct 6 ms 384 KB Output is correct
30 Correct 6 ms 512 KB Output is correct
31 Correct 6 ms 384 KB Output is correct
32 Correct 6 ms 384 KB Output is correct
33 Correct 427 ms 61140 KB Output is correct
34 Correct 549 ms 69984 KB Output is correct
35 Correct 506 ms 61244 KB Output is correct
36 Correct 481 ms 65168 KB Output is correct
37 Correct 63 ms 27768 KB Output is correct
38 Correct 61 ms 27768 KB Output is correct
39 Correct 313 ms 69856 KB Output is correct
40 Correct 300 ms 69832 KB Output is correct
41 Correct 54 ms 25976 KB Output is correct
42 Correct 279 ms 62048 KB Output is correct
43 Correct 49 ms 25856 KB Output is correct
44 Correct 275 ms 64992 KB Output is correct
45 Correct 49 ms 25848 KB Output is correct
46 Correct 53 ms 25856 KB Output is correct
47 Correct 261 ms 65372 KB Output is correct
48 Correct 262 ms 65376 KB Output is correct
49 Correct 229 ms 28844 KB Output is correct
50 Correct 230 ms 28844 KB Output is correct
51 Correct 456 ms 70212 KB Output is correct
52 Correct 403 ms 70048 KB Output is correct
53 Correct 258 ms 27052 KB Output is correct
54 Correct 345 ms 62052 KB Output is correct
55 Correct 164 ms 25984 KB Output is correct
56 Correct 410 ms 64992 KB Output is correct
57 Correct 141 ms 25984 KB Output is correct
58 Correct 226 ms 26020 KB Output is correct
59 Correct 275 ms 65376 KB Output is correct