Submission #580809

#	Time	Username	Problem	Language	Result	Execution time	Memory
580809		MohamedFaresNebili	Horses (IOI15_horses)	C++14	100 / 100	1193 ms	97516 KiB

horses

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = __int128;
        using ii = pair<int, int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        const ll MOD = 1e9 + 7;
        const ll MX  = 1e9;

        ll N, X[500001], Y[500001], st[2000005], ST[2000005]; set<ll> S;
        void build(ll v, ll l, ll r) {
            if(l == r) {
                st[v] = X[l]; ST[v] = Y[l];
                return;
            }
            build(v * 2, l, (l + r) / 2);
            build(v * 2 + 1, (l + r) / 2 + 1, r);
            st[v] = st[v * 2] * st[v * 2 + 1] % MOD;
            ST[v] = max(ST[v * 2], ST[v * 2 + 1]);
        }
        void update(ll v, ll l, ll r, ll p) {
            if(l == r) {
                st[v] = X[l], ST[v] = Y[l];
                return;
            }
            ll md = (l + r) / 2;
            if(p <= md) update(v * 2, l, md, p);
            else update(v * 2 + 1, md + 1, r, p);
            st[v] = st[v * 2] * st[v * 2 + 1] % MOD;
            ST[v] = max(ST[v * 2], ST[v * 2 + 1]);
        }
        ll query(ll v, ll l, ll r, ll lo, ll hi) {
            if(l > hi || r < lo) return 1;
            if(l >= lo && r <= hi) return st[v];
            return query(v * 2, l, (l + r) / 2, lo, hi) * query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi) % MOD;
        }
        ll Query(ll v, ll l, ll r, ll lo, ll hi) {
            if(l > hi || r < lo) return 0;
            if(l >= lo && r <= hi) return ST[v];
            return max(Query(v * 2, l, (l + r) / 2, lo, hi),
                       Query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
        }
        ll solve() {
            if(S.empty()) return ST[1];
            auto it = S.end(); it--;
            ll v = 1; vector<ll> arr;
            while(v <= MX) {
                v *= X[*it]; arr.pb(*it);
                if(it == S.begin()) break;
                it--;
            }
            reverse(arr.begin(), arr.end());
            v = 1; ll best = 0;
            for(ll l = 0; l < (ll)arr.size(); l++) {
                v *= X[arr[l]];
                best = max(best, v * Y[arr[l]]);
                if(l < arr.size() - 1)
                    best = max(best, v * Query(1, 0, N - 1, arr[l], arr[l + 1] - 1));
                else best = max(best, v * Query(1, 0, N - 1, arr[l], N - 1));
            }
            if(v <= MX) best = max(best, Query(1, 0, N - 1, 0, arr[0] - 1)), best %= MOD;
            else best = best % MOD * query(1, 0, N - 1, 0, arr[0] - 1) % MOD;
            return best;
        }
        int init(int n, int x[], int y[]) {
            N = n;
            for(int l = 0; l < N; l++) {
                X[l] = x[l], Y[l] = y[l];
                if(X[l] > 1) S.insert(l);
            }
            build(1, 0, N - 1);
            return solve() % MOD;
        }
        int updateX(int pos, int val) {
            if(X[pos] > 1) S.erase(pos);
            X[pos] = val;
            if(X[pos] > 1) S.insert(pos);
            update(1, 0, N - 1, pos);
            return solve() % MOD;
        }
        int updateY(int pos, int val) {
            Y[pos] = val;
            update(1, 0, N - 1, pos);
            return solve() % MOD;
        }

Compilation message (stderr)

horses.cpp: In function 'll solve()':
horses.cpp:66:28: warning: conversion from 'll' {aka '__int128'} to 'std::vector<__int128>::size_type' {aka 'long unsigned int'} may change value [-Wconversion]
   66 |                 v *= X[arr[l]];
      |                            ^
horses.cpp:67:44: warning: conversion from 'll' {aka '__int128'} to 'std::vector<__int128>::size_type' {aka 'long unsigned int'} may change value [-Wconversion]
   67 |                 best = max(best, v * Y[arr[l]]);
      |                                            ^
horses.cpp:69:65: warning: conversion from 'll' {aka '__int128'} to 'std::vector<__int128>::size_type' {aka 'long unsigned int'} may change value [-Wconversion]
   69 |                     best = max(best, v * Query(1, 0, N - 1, arr[l], arr[l + 1] - 1));
      |                                                                 ^
horses.cpp:69:75: warning: conversion from 'll' {aka '__int128'} to 'std::vector<__int128>::size_type' {aka 'long unsigned int'} may change value [-Wconversion]
   69 |                     best = max(best, v * Query(1, 0, N - 1, arr[l], arr[l + 1] - 1));
      |                                                                         ~~^~~
horses.cpp:70:66: warning: conversion from 'll' {aka '__int128'} to 'std::vector<__int128>::size_type' {aka 'long unsigned int'} may change value [-Wconversion]
   70 |                 else best = max(best, v * Query(1, 0, N - 1, arr[l], N - 1));
      |                                                                  ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:83:28: warning: conversion from 'll' {aka '__int128'} to 'int' may change value [-Wconversion]
   83 |             return solve() % MOD;
      |                    ~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:90:28: warning: conversion from 'll' {aka '__int128'} to 'int' may change value [-Wconversion]
   90 |             return solve() % MOD;
      |                    ~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:95:28: warning: conversion from 'll' {aka '__int128'} to 'int' may change value [-Wconversion]
   95 |             return solve() % MOD;
      |                    ~~~~~~~~^~~~~

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