oj.uz

Submission #580808

# Submission time Handle Problem Language Result Execution time Memory
580808 2022-06-21T21:16:28 Z MohamedFaresNebili Horses (IOI15_horses) C++14
17 / 100
 605 ms 65500 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        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

horses.cpp: In function 'll solve()':
horses.cpp:68:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                 if(l < arr.size() - 1)
      |                    ~~^~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:83:28: warning: conversion from 'll' {aka 'long long int'} 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 'long long int'} 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 'long long int'} to 'int' may change value [-Wconversion]
   95 |             return solve() % MOD;
      |                    ~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 312 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Incorrect 2 ms 324 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 56680 KB Output is correct
2 Incorrect 384 ms 65500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 312 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 308 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Incorrect 2 ms 340 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 304 KB Output is correct
22 Correct 1 ms 308 KB Output is correct
23 Incorrect 1 ms 340 KB Output isn't correct
24 Halted 0 ms 0 KB -