oj.uz

Submission #1099212

# Submission time Handle Problem Language Result Execution time Memory
1099212 2024-10-10T19:17:22 Z Tymond Horses (IOI15_horses) C++17
17 / 100
 753 ms 57168 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;
set<pii> bad;
pii tree2[2 * BASE + 7];//max query (Y)
ll tree[2 * BASE + 7];//mnożenie modulo
ll lazy[2 * BASE + 7];//lazy mnożenie modulo

ll inv(ll a){
    if(a <= 1){
        return a;
    }
    return (ll)MOD - (ll)(MOD / a) * inv(MOD % a) % MOD;
}

void Push(int v){
    tree[2 * v] = (ll)tree[2 * v] * lazy[v] % MOD;
    tree[2 * v + 1] = (ll)tree[2 * v + 1] * lazy[v] % MOD;
    lazy[2 * v] = (ll)lazy[2 * v] * lazy[v] % MOD;
    lazy[2 * v + 1] = (ll)lazy[2 * v + 1] * lazy[v] % MOD;
    lazy[v] = 1LL;
}

//find mx w tablicy y
pii getMx(int v, int l, int p, int a, int b){
    if(b < l || p < a){
        return {0, a};
    }

    if(a <= l && p <= b){
        return tree2[v];
    }

    int mid = (l + p) / 2;
    pii res1 = getMx(2 * v, l, mid, a, b);
    pii res2 = getMx(2 * v + 1, mid + 1, p, a, b);
    if(res1.fi > res2.fi){
        return res1;
    }
    return res2;
}

//iloczyn xl * ... * xp
ll query(int v, int l, int p, int a){
    if(l == p){
        return tree[v];
    }

    Push(v);
    int mid = (l + p) / 2;
    if(a <= mid){
        return query(2 * v, l, mid, a);
    }else{
        return query(2 * v + 1, mid + 1, p, a);
    }
}

void upd(int v, int l, int p, int ind, ll val){
    tree[v] = (ll)tree[v] * val % MOD;
    if(l == p){
        return;
    }

    Push(v);
    int mid = (l + p) / 2;
    if(ind <= mid){
        upd(2 * v, l, mid, ind, val);
    }else{
        upd(2 * v + 1, mid + 1, p, ind, val);
    }
}

//get result
ll solve(){
    vi usu;
    while(sz(ok) && sz(usu) < 30){
        usu.pb(*(--ok.end()));
        ok.erase(--ok.end());
    }

    reverse(all(usu));

    if(sz(usu) == 0){
        return getMx(1, 0, BASE - 1, 0, n - 1).fi;
    }

    auto it = bad.lower_bound({usu[0], 0});
    ll mul = 1LL;
    int best = usu[0];
    for(auto ele : usu){
        mul = (ll)mul * x[ele];
        if(mul > MOD){
            best = ele;
            mul = 1LL;
        }else if((ll)mul * y[ele] > y[best]){
            best = ele;
            mul = 1LL;
        }

        if(it != bad.end() && (*it).fi == ele + 1){
            pii now = getMx(1, 0, BASE - 1,(*it).fi, (*it).se);
            //cout << mul << ' ' << now.fi<< ' ' << now.se << '\n';
            if((ll)mul * now.fi > y[best]){
                mul = 1LL;
                best = now.se;
            }
            it++;
        }
    }

    for(auto ele : usu){
        ok.insert(ele);
    }
    //cout << best << ' ' << y[best] << ' ' << query(1, 0, BASE - 1, best) << '\n';
    return (ll)y[best] * query(1, 0, BASE - 1, best) % 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] = lazy[i] = 1LL;
    }

    ll mul = 1LL;
    for(int i = 0; i < n; i++){
        tree2[i + BASE] = {y[i], i};
        mul = (ll)mul * x[i];
        mul %= MOD;
        tree[i + BASE] = mul;
    }

    for(int i = BASE - 1; i >= 1; i--){
        tree[i] = (ll)tree[2 * i] * tree[2 * i + 1] % MOD;
        if(tree2[2 * i].fi > tree2[2 * i + 1].fi){
            tree2[i] = tree2[2 * i];
        }else{
            tree2[i] = tree2[2 * i + 1];
        }
    }

    int i = 0;
    for(i = 0; i < n; i++){
        if(x[i] > 1){
            ok.insert(i);
            continue;
        }
        int b = i;
        while(i + 1 < n && x[i + 1] == 1){
            i++;
        }
        bad.insert({b, i});
    }

    return (int)solve();
}

int updateX(int pos, int val){
    if(x[pos] == 1){
        if(val == 1){
            return (int)solve();
        }

        //prevVal == 1 ^ val > 1
        auto it = bad.upper_bound({pos, 0});
        --it;
        pii akt = *it;
        bad.erase(it);
        if(akt.fi != pos){
            bad.insert({akt.fi, pos - 1});
        }

        if(akt.se != pos){
            bad.insert({pos + 1, akt.se});
        }

        ok.insert(pos);
        upd(1, 0, BASE - 1,pos, (ll)val * inv(x[pos]) % MOD);
        x[pos] = val;
    }else{
        if(val > 1){
            upd(1, 0, BASE - 1, pos, (ll)val * inv(x[pos]) % MOD);
            x[pos] = val;
            return (int)solve();
        }

        //prevVal > 1 ^ val == 1
        upd(1, 0, BASE - 1, pos, inv(x[pos]));
        x[pos] = 1;
        pii d = {pos, pos};
        if(sz(bad)){
            auto it = bad.lower_bound({pos, 0});
            if(it != bad.end() && (*it).fi == pos + 1){
                d.se = (*it).se;
                bad.erase(it);
            }
            auto it2 = bad.lower_bound({pos, 0});
            if(it2 != bad.begin()){
                --it2;
                if((*it2).se == pos - 1){
                    d.fi = (*it2).fi;
                    bad.erase(it2);
                }
            }
        }
        bad.insert(d);
    }
    return (int)solve();
}

int updateY(int pos, int val){
    y[pos] = val;
    tree2[pos + BASE] = {val, pos};
    pos += BASE;
    pos /= 2;
    while(pos > 0){
        if(tree2[2 * pos].fi > tree2[2 * pos + 1].fi){
            tree2[pos] = tree2[2 * pos];
        }else{
            tree2[pos] = tree2[2 * pos + 1];
        }
        pos /= 2;
    }

    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 9 ms 20824 KB Output is correct
2 Correct 9 ms 20828 KB Output is correct
3 Correct 9 ms 20756 KB Output is correct
4 Correct 9 ms 20828 KB Output is correct
5 Correct 9 ms 20828 KB Output is correct
6 Correct 11 ms 20824 KB Output is correct
7 Correct 9 ms 20828 KB Output is correct
8 Correct 9 ms 20768 KB Output is correct
9 Correct 9 ms 20776 KB Output is correct
10 Correct 9 ms 20828 KB Output is correct
11 Correct 9 ms 20828 KB Output is correct
12 Correct 9 ms 20824 KB Output is correct
13 Correct 9 ms 20812 KB Output is correct
14 Correct 13 ms 20828 KB Output is correct
15 Correct 9 ms 20828 KB Output is correct
16 Correct 10 ms 20824 KB Output is correct
17 Correct 10 ms 20828 KB Output is correct
18 Correct 10 ms 20912 KB Output is correct
19 Correct 11 ms 20824 KB Output is correct
20 Correct 10 ms 20828 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20824 KB Output is correct
2 Correct 10 ms 20824 KB Output is correct
3 Correct 11 ms 20920 KB Output is correct
4 Correct 11 ms 20824 KB Output is correct
5 Correct 10 ms 20828 KB Output is correct
6 Correct 10 ms 20828 KB Output is correct
7 Correct 10 ms 20828 KB Output is correct
8 Correct 11 ms 20828 KB Output is correct
9 Correct 14 ms 20920 KB Output is correct
10 Correct 10 ms 20828 KB Output is correct
11 Correct 14 ms 20740 KB Output is correct
12 Correct 10 ms 20824 KB Output is correct
13 Correct 10 ms 20984 KB Output is correct
14 Correct 9 ms 20828 KB Output is correct
15 Correct 10 ms 20824 KB Output is correct
16 Correct 10 ms 20828 KB Output is correct
17 Correct 10 ms 21076 KB Output is correct
18 Correct 10 ms 20828 KB Output is correct
19 Correct 10 ms 20908 KB Output is correct
20 Correct 10 ms 20828 KB Output is correct
21 Incorrect 9 ms 20828 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 57168 KB Output is correct
2 Incorrect 753 ms 57168 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20824 KB Output is correct
2 Correct 11 ms 20828 KB Output is correct
3 Correct 10 ms 20828 KB Output is correct
4 Correct 10 ms 20828 KB Output is correct
5 Correct 11 ms 20936 KB Output is correct
6 Correct 10 ms 20828 KB Output is correct
7 Correct 11 ms 20828 KB Output is correct
8 Correct 9 ms 20824 KB Output is correct
9 Correct 10 ms 20828 KB Output is correct
10 Correct 10 ms 20828 KB Output is correct
11 Correct 9 ms 20980 KB Output is correct
12 Correct 9 ms 20828 KB Output is correct
13 Correct 11 ms 20828 KB Output is correct
14 Correct 10 ms 21000 KB Output is correct
15 Correct 11 ms 20828 KB Output is correct
16 Correct 10 ms 20996 KB Output is correct
17 Correct 10 ms 20828 KB Output is correct
18 Correct 14 ms 20824 KB Output is correct
19 Correct 10 ms 20824 KB Output is correct
20 Correct 10 ms 20828 KB Output is correct
21 Incorrect 10 ms 20828 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20868 KB Output is correct
2 Correct 10 ms 20828 KB Output is correct
3 Correct 11 ms 20828 KB Output is correct
4 Correct 10 ms 20824 KB Output is correct
5 Correct 10 ms 20828 KB Output is correct
6 Correct 9 ms 20828 KB Output is correct
7 Correct 10 ms 20936 KB Output is correct
8 Correct 9 ms 20860 KB Output is correct
9 Correct 10 ms 20828 KB Output is correct
10 Correct 11 ms 20828 KB Output is correct
11 Correct 10 ms 20856 KB Output is correct
12 Correct 10 ms 20828 KB Output is correct
13 Correct 10 ms 20940 KB Output is correct
14 Correct 10 ms 20828 KB Output is correct
15 Correct 9 ms 20828 KB Output is correct
16 Correct 10 ms 20828 KB Output is correct
17 Correct 10 ms 20828 KB Output is correct
18 Correct 10 ms 20828 KB Output is correct
19 Correct 10 ms 20828 KB Output is correct
20 Correct 9 ms 20828 KB Output is correct
21 Incorrect 10 ms 20824 KB Output isn't correct
22 Halted 0 ms 0 KB -