Submission #563623

#	Time	Username	Problem	Language	Result	Execution time	Memory
563623		hoanghq2004	Horses (IOI15_horses)	C++14	100 / 100	924 ms	51256 KiB

horses

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "horses.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 1e9 + 7;
const int N = 5e5 + 10;

int n, st[N * 4];
int BIT[N];

int power(int a, int n) {
    int ans = 1;
    for (; n; n >>= 1, a = 1LL * a * a % mod)
        if (n & 1) ans = 1LL * ans * a % mod;
    return ans;
}

void add(int i, int mul) {
    for (++i; i < N; i += i & - i) BIT[i] = 1LL * BIT[i] * mul % mod;
}

int get(int i) {
    int ans = 1;
    for (++i; i; i -= i & - i) ans = 1LL * ans * BIT[i] % mod;
    return ans;
}

void add(int id, int L, int R, int i, int val) {
    if (L == R) {
        st[id] = val;
        return;
    }
    int mid = L + R >> 1;
    if (i <= mid) add(id * 2, L, mid, i, val);
    else add(id * 2 + 1, mid + 1, R, i, val);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}

int get(int id, int L, int R, int u, int v) {
    if (u > R || L > v) return -1;
    if (u <= L && R <= v) return st[id];
    int mid = L + R >> 1;
    return max(get(id * 2, L, mid, u, v), get(id * 2 + 1, mid + 1, R, u, v));
}

set <int> s;
int x[N], y[N];

int solve() {
    int cur = n;
    long long mul = 1, p = 1;
    int best = -1;
    int i = -1;
    while (1) {
        int last = *(--s.lower_bound(cur));
        int val = get(1, 0, n - 1, last, cur - 1);
        if (best == -1 || 1.0L * best * p < val) {
            best = val;
            i = last;
            p = 1;
        }
        p *= x[last];
        if (mul > 1e9) break;
        mul *= x[last];
        cur = last;
        if (cur == 0) break;
    }
    int j = (*(--s.end()) == i ? n : *s.upper_bound(i));
    return 1LL * get(i) * get(1, 0, n - 1, i, j - 1) % mod;
}

int init(int _n, int X[], int Y[]) {
    n = _n;
    for (int i = 0; i < n; ++i) x[i] = X[i], y[i] = Y[i];

    s.insert(0);
    for (int i = 0; i < n; ++i) if (x[i] != 1) s.insert(i);
    for (int i = 0; i < n; ++i) BIT[i + 1] = 1;
    for (int i = 0; i < n; ++i) add(i, x[i]);
    for (int i = 0; i < n; ++i) add(1, 0, n - 1, i, y[i]);
    return solve();
}

int updateX(int i, int val) {
    if (x[i] != 1 && i) s.erase(i);
    add(i, power(x[i], mod - 2));
    x[i] = val;
    if (x[i] != 1 && i) s.insert(i);
    add(i, x[i]);
    return solve();
}

int updateY(int i, int val) {
    add(1, 0, n - 1, i, val);
    y[i] = val;
    return solve();
}

//
//int main() {
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
//    ios :: sync_with_stdio(0); cin.tie(0);
//
//    int n, m;
//    cin >> n;
//    int x[n], y[n];
//    for (int i = 0; i < n; ++i) cin >> x[i];
//    for (int i = 0; i < n; ++i) cin >> y[i];
//    cin >> m;
//    cout << init(n, x, y) << '\n';
//    while (m--) {
//        int cmd, i, val;
//        cin >> cmd >> i >> val;
//        if (cmd == 1) cout << updateX(i, val) << '\n';
//        else cout << updateY(i, val) << '\n';
//    }
//    cerr << solve() << '\n';
//}

Compilation message (stderr)

horses.cpp: In function 'int power(int, int)':
horses.cpp:20:22: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   20 | int power(int a, int n) {
      |                  ~~~~^
horses.cpp:17:5: note: shadowed declaration is here
   17 | int n, st[N * 4];
      |     ^
horses.cpp:22:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 |     for (; n; n >>= 1, a = 1LL * a * a % mod)
      |                            ~~~~~~~~~~~~^~~~~
horses.cpp:23:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   23 |         if (n & 1) ans = 1LL * ans * a % mod;
      |                          ~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void add(int, int)':
horses.cpp:28:64: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   28 |     for (++i; i < N; i += i & - i) BIT[i] = 1LL * BIT[i] * mul % mod;
      |                                             ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int get(int)':
horses.cpp:33:57: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   33 |     for (++i; i; i -= i & - i) ans = 1LL * ans * BIT[i] % mod;
      |                                      ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void add(int, int, int, int, int)':
horses.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int mid = L + R >> 1;
      |               ~~^~~
horses.cpp: In function 'int get(int, int, int, int, int)':
horses.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = L + R >> 1;
      |               ~~^~~
horses.cpp: In function 'int solve()':
horses.cpp:72:13: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   72 |         if (mul > 1e9) break;
      |             ^~~
horses.cpp:78:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   78 |     return 1LL * get(i) * get(1, 0, n - 1, i, j - 1) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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