oj.uz

Submission #1099506

# Submission time Handle Problem Language Result Execution time Memory
1099506 2024-10-11T13:34:39 Z Tymond Horses (IOI15_horses) C++17
100 / 100
 1142 ms 61728 KB 
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
 
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
 
const int MOD = 1e9 + 7;
const int MAXN = 5e5 + 7;
const int BASE = (1 << 19);
int x[MAXN];
int y[MAXN];
int n;
set<int> ok;
pll tree[2 * BASE + 7];//.fi -> mnożenie .se -> max y
 
pll merge(pll a, pll b){
    return mp((ll)a.fi * b.fi % MOD, (ll)max(a.se, b.se));
}
 
pll query(int v, int l, int p, int a, int b){
    if(b < l || p < a){
        return mp(1LL, 0LL);
    }
 
    if(a <= l && p <= b){
        return tree[v];
    }
 
    int mid = (l + p) / 2;
    return merge(query(2 * v, l, mid, a, b), query(2 * v + 1, mid + 1, p, a, b));
}
 
void upd(int ind){
    tree[ind + BASE] = {x[ind], y[ind]};
    ind += BASE;
    ind /= 2;
    while(ind > 0){
        tree[ind] = merge(tree[2 * ind], tree[2 * ind + 1]);
        ind /= 2;
    }
}
 
//get result
ll solve(){
    vi usu;
    while(sz(ok) && sz(usu) < 30){
        usu.pb(*(--ok.end()));
        ok.erase(--ok.end());
    }
    bool f = 0;
    if(sz(usu) == 0 || usu.back() != 0){
        usu.pb(0);
        f = 1;
    }
    reverse(all(usu));
 
    ll mul = 1LL;
    int yBest = 0;
    int best = n - 1;
    for(int i = 0; i < sz(usu); i++){
        int nxt = (i == sz(usu) - 1 ? n - 1 : usu[i + 1] - 1);
        int aktY = (int)query(1, 0, BASE - 1, usu[i], nxt).se;
        mul = (ll)mul * x[usu[i]];
        if(mul > MOD){
            mul = 1LL;
            yBest = aktY;
            best = usu[i];
        }else if((ll)mul * aktY > yBest){
            mul = 1LL;
            yBest = aktY;
            best = usu[i];
        }
    }
 
    for(auto ele : usu){
        if(ele == 0 && f){
            continue;
        }
        ok.insert(ele);
    }
 
    return (ll)yBest * query(1, 0, BASE - 1, 0, best).fi % MOD;
}
 
int init(int N, int Xn[], int Yn[]){
    n = N;
    for(int i = 0; i < n; i++){
        x[i] = Xn[i];
        y[i] = Yn[i];
    }
 
    for(int i = 1; i < 2 * BASE + 7; i++){
        tree[i] = mp(1LL, 0LL);
    }
 
    for(int i = 0; i < n; i++){
        tree[i + BASE] = {x[i], y[i]};
    }
 
    for(int i = BASE - 1; i >= 1; i--){
        tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }
 
    for(int i = 0; i < n; i++){
        if(x[i] > 1){
            ok.insert(i);
        }
    }
 
    return (int)solve();
}
 
int updateX(int pos, int val){
    if(x[pos] > 1){
        ok.erase(pos);
    }
    x[pos] = val;
    if(x[pos] > 1){
        ok.insert(pos);
    }
    upd(pos);
 
    return (int)solve();
}
 
int updateY(int pos, int val){
    y[pos] = val;
    upd(pos);
 
    return (int)solve();
}
 
/*int main(){
    int p[3] = {2, 1, 3};
    int d[3] = {3, 4, 1};
    cout << init(3, p, d) << '\n';
    cout << updateY(1, 2) << '\n';
 
    return 0;
}*/

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16728 KB Output is correct
2 Correct 7 ms 16732 KB Output is correct
3 Correct 7 ms 16732 KB Output is correct
4 Correct 7 ms 16720 KB Output is correct
5 Correct 7 ms 16732 KB Output is correct
6 Correct 8 ms 16848 KB Output is correct
7 Correct 7 ms 16728 KB Output is correct
8 Correct 7 ms 16832 KB Output is correct
9 Correct 7 ms 16732 KB Output is correct
10 Correct 7 ms 16732 KB Output is correct
11 Correct 7 ms 16876 KB Output is correct
12 Correct 7 ms 16732 KB Output is correct
13 Correct 8 ms 16776 KB Output is correct
14 Correct 9 ms 16732 KB Output is correct
15 Correct 7 ms 16732 KB Output is correct
16 Correct 7 ms 16876 KB Output is correct
17 Correct 7 ms 16732 KB Output is correct
18 Correct 7 ms 16692 KB Output is correct
19 Correct 7 ms 16732 KB Output is correct
20 Correct 7 ms 16732 KB Output is correct
21 Correct 7 ms 16728 KB Output is correct
22 Correct 8 ms 16732 KB Output is correct
23 Correct 15 ms 16932 KB Output is correct
24 Correct 15 ms 16732 KB Output is correct
25 Correct 14 ms 16972 KB Output is correct
26 Correct 13 ms 16732 KB Output is correct
27 Correct 14 ms 16912 KB Output is correct
28 Correct 14 ms 16732 KB Output is correct
29 Correct 8 ms 16732 KB Output is correct
30 Correct 13 ms 16732 KB Output is correct
31 Correct 11 ms 16864 KB Output is correct
32 Correct 12 ms 16832 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1100 ms 50772 KB Output is correct
2 Correct 1130 ms 61644 KB Output is correct
3 Correct 1053 ms 52892 KB Output is correct
4 Correct 1062 ms 56660 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16728 KB Output is correct
2 Correct 7 ms 16732 KB Output is correct
3 Correct 7 ms 16732 KB Output is correct
4 Correct 7 ms 16732 KB Output is correct
5 Correct 6 ms 16732 KB Output is correct
6 Correct 7 ms 16732 KB Output is correct
7 Correct 7 ms 16732 KB Output is correct
8 Correct 7 ms 16816 KB Output is correct
9 Correct 7 ms 16732 KB Output is correct
10 Correct 8 ms 16732 KB Output is correct
11 Correct 7 ms 16732 KB Output is correct
12 Correct 7 ms 16812 KB Output is correct
13 Correct 7 ms 16848 KB Output is correct
14 Correct 6 ms 16732 KB Output is correct
15 Correct 7 ms 16732 KB Output is correct
16 Correct 7 ms 16732 KB Output is correct
17 Correct 7 ms 16732 KB Output is correct
18 Correct 7 ms 16732 KB Output is correct
19 Correct 7 ms 16732 KB Output is correct
20 Correct 7 ms 16732 KB Output is correct
21 Correct 7 ms 16884 KB Output is correct
22 Correct 7 ms 16732 KB Output is correct
23 Correct 14 ms 16860 KB Output is correct
24 Correct 13 ms 16732 KB Output is correct
25 Correct 13 ms 16728 KB Output is correct
26 Correct 13 ms 16732 KB Output is correct
27 Correct 14 ms 16788 KB Output is correct
28 Correct 14 ms 16732 KB Output is correct
29 Correct 8 ms 16732 KB Output is correct
30 Correct 14 ms 16728 KB Output is correct
31 Correct 11 ms 16928 KB Output is correct
32 Correct 12 ms 16728 KB Output is correct
33 Correct 107 ms 28752 KB Output is correct
34 Correct 93 ms 28756 KB Output is correct
35 Correct 250 ms 58952 KB Output is correct
36 Correct 243 ms 58964 KB Output is correct
37 Correct 102 ms 26796 KB Output is correct
38 Correct 174 ms 39760 KB Output is correct
39 Correct 28 ms 26708 KB Output is correct
40 Correct 225 ms 54096 KB Output is correct
41 Correct 60 ms 26764 KB Output is correct
42 Correct 80 ms 26640 KB Output is correct
43 Correct 141 ms 54352 KB Output is correct
44 Correct 140 ms 54356 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16732 KB Output is correct
2 Correct 6 ms 16808 KB Output is correct
3 Correct 7 ms 16888 KB Output is correct
4 Correct 7 ms 16744 KB Output is correct
5 Correct 7 ms 16732 KB Output is correct
6 Correct 6 ms 16732 KB Output is correct
7 Correct 6 ms 16732 KB Output is correct
8 Correct 6 ms 16732 KB Output is correct
9 Correct 6 ms 16732 KB Output is correct
10 Correct 6 ms 16788 KB Output is correct
11 Correct 7 ms 16732 KB Output is correct
12 Correct 6 ms 16732 KB Output is correct
13 Correct 6 ms 16732 KB Output is correct
14 Correct 7 ms 16848 KB Output is correct
15 Correct 8 ms 16732 KB Output is correct
16 Correct 7 ms 16808 KB Output is correct
17 Correct 7 ms 16720 KB Output is correct
18 Correct 8 ms 16712 KB Output is correct
19 Correct 9 ms 16732 KB Output is correct
20 Correct 7 ms 16760 KB Output is correct
21 Correct 8 ms 16732 KB Output is correct
22 Correct 7 ms 16732 KB Output is correct
23 Correct 16 ms 16728 KB Output is correct
24 Correct 12 ms 16728 KB Output is correct
25 Correct 13 ms 16924 KB Output is correct
26 Correct 13 ms 16728 KB Output is correct
27 Correct 13 ms 16732 KB Output is correct
28 Correct 14 ms 16728 KB Output is correct
29 Correct 8 ms 16732 KB Output is correct
30 Correct 14 ms 16880 KB Output is correct
31 Correct 11 ms 16984 KB Output is correct
32 Correct 12 ms 16912 KB Output is correct
33 Correct 1118 ms 52904 KB Output is correct
34 Correct 1049 ms 61728 KB Output is correct
35 Correct 960 ms 53072 KB Output is correct
36 Correct 974 ms 56656 KB Output is correct
37 Correct 104 ms 28612 KB Output is correct
38 Correct 87 ms 28608 KB Output is correct
39 Correct 233 ms 58964 KB Output is correct
40 Correct 245 ms 58960 KB Output is correct
41 Correct 103 ms 26804 KB Output is correct
42 Correct 167 ms 39512 KB Output is correct
43 Correct 26 ms 26704 KB Output is correct
44 Correct 214 ms 54100 KB Output is correct
45 Correct 59 ms 26704 KB Output is correct
46 Correct 73 ms 26716 KB Output is correct
47 Correct 129 ms 54356 KB Output is correct
48 Correct 139 ms 54356 KB Output is correct
49 Correct 784 ms 31796 KB Output is correct
50 Correct 688 ms 31828 KB Output is correct
51 Correct 1142 ms 60948 KB Output is correct
52 Correct 1120 ms 60496 KB Output is correct
53 Correct 806 ms 30032 KB Output is correct
54 Correct 1076 ms 43516 KB Output is correct
55 Correct 114 ms 27728 KB Output is correct
56 Correct 1014 ms 55792 KB Output is correct
57 Correct 428 ms 28244 KB Output is correct
58 Correct 593 ms 28928 KB Output is correct
59 Correct 150 ms 54392 KB Output is correct