oj.uz

Submission #1099214

# Submission time Handle Problem Language Result Execution time Memory
1099214 2024-10-10T19:26:07 Z Tymond Horses (IOI15_horses) C++17
37 / 100
 768 ms 64680 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 a, int b, ll val){
    if(p < a || b < l){
        return;
    }
    tree[v] = (ll)tree[v] * val % MOD;
    if(a <= l && p <= b){
        lazy[v] = (ll)lazy[v] * val % MOD;
        return;
    }

    Push(v);
    int mid = (l + p) / 2;
    upd(2 * v, l, mid, a, b, val);
    upd(2 * v + 1, mid + 1, p, a, b, 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, n - 1, val);
        x[pos] = val;
    }else{
        if(val > 1){
            upd(1, 0, BASE - 1, pos, n - 1, (ll)val * inv(x[pos]) % MOD);
            x[pos] = val;
            return (int)solve();
        }

        //prevVal > 1 ^ val == 1
        upd(1, 0, BASE - 1, pos, n - 1, 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 11 ms 20828 KB Output is correct
2 Correct 12 ms 20956 KB Output is correct
3 Correct 11 ms 20828 KB Output is correct
4 Correct 11 ms 20872 KB Output is correct
5 Correct 12 ms 20828 KB Output is correct
6 Correct 11 ms 20756 KB Output is correct
7 Correct 9 ms 20788 KB Output is correct
8 Correct 10 ms 20828 KB Output is correct
9 Correct 10 ms 20744 KB Output is correct
10 Correct 10 ms 20824 KB Output is correct
11 Correct 10 ms 20824 KB Output is correct
12 Correct 11 ms 20828 KB Output is correct
13 Correct 11 ms 20828 KB Output is correct
14 Correct 10 ms 20824 KB Output is correct
15 Correct 11 ms 20828 KB Output is correct
16 Correct 10 ms 20816 KB Output is correct
17 Correct 10 ms 20828 KB Output is correct
18 Correct 9 ms 20824 KB Output is correct
19 Correct 10 ms 20796 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 14 ms 20876 KB Output is correct
2 Correct 11 ms 20828 KB Output is correct
3 Correct 11 ms 20796 KB Output is correct
4 Correct 10 ms 20968 KB Output is correct
5 Correct 10 ms 20828 KB Output is correct
6 Correct 10 ms 20828 KB Output is correct
7 Correct 11 ms 20828 KB Output is correct
8 Correct 10 ms 20980 KB Output is correct
9 Correct 10 ms 20964 KB Output is correct
10 Correct 10 ms 20828 KB Output is correct
11 Correct 10 ms 20828 KB Output is correct
12 Correct 10 ms 20744 KB Output is correct
13 Correct 10 ms 20824 KB Output is correct
14 Correct 11 ms 20980 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 20924 KB Output is correct
18 Correct 11 ms 20828 KB Output is correct
19 Correct 9 ms 20828 KB Output is correct
20 Correct 10 ms 20852 KB Output is correct
21 Correct 10 ms 20924 KB Output is correct
22 Correct 11 ms 20828 KB Output is correct
23 Incorrect 15 ms 20828 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 57028 KB Output is correct
2 Correct 768 ms 57172 KB Output is correct
3 Correct 752 ms 60756 KB Output is correct
4 Correct 739 ms 64680 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20828 KB Output is correct
2 Correct 9 ms 20984 KB Output is correct
3 Correct 9 ms 20828 KB Output is correct
4 Correct 10 ms 20828 KB Output is correct
5 Correct 10 ms 20828 KB Output is correct
6 Correct 9 ms 20828 KB Output is correct
7 Correct 9 ms 20888 KB Output is correct
8 Correct 9 ms 20828 KB Output is correct
9 Correct 9 ms 20828 KB Output is correct
10 Correct 9 ms 20880 KB Output is correct
11 Correct 9 ms 20748 KB Output is correct
12 Correct 10 ms 20828 KB Output is correct
13 Correct 10 ms 20860 KB Output is correct
14 Correct 11 ms 20828 KB Output is correct
15 Correct 12 ms 20816 KB Output is correct
16 Correct 9 ms 20768 KB Output is correct
17 Correct 9 ms 20824 KB Output is correct
18 Correct 9 ms 20828 KB Output is correct
19 Correct 9 ms 20840 KB Output is correct
20 Correct 9 ms 20828 KB Output is correct
21 Correct 9 ms 20924 KB Output is correct
22 Correct 9 ms 20828 KB Output is correct
23 Incorrect 14 ms 20828 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20828 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 20876 KB Output is correct
5 Correct 10 ms 20828 KB Output is correct
6 Correct 10 ms 20824 KB Output is correct
7 Correct 10 ms 20784 KB Output is correct
8 Correct 11 ms 21076 KB Output is correct
9 Correct 10 ms 20836 KB Output is correct
10 Correct 9 ms 20824 KB Output is correct
11 Correct 9 ms 20828 KB Output is correct
12 Correct 10 ms 20964 KB Output is correct
13 Correct 10 ms 20828 KB Output is correct
14 Correct 10 ms 20844 KB Output is correct
15 Correct 10 ms 20884 KB Output is correct
16 Correct 11 ms 20824 KB Output is correct
17 Correct 10 ms 20828 KB Output is correct
18 Correct 10 ms 20828 KB Output is correct
19 Correct 9 ms 20880 KB Output is correct
20 Correct 10 ms 20828 KB Output is correct
21 Correct 10 ms 20828 KB Output is correct
22 Correct 10 ms 20936 KB Output is correct
23 Incorrect 14 ms 20828 KB Output isn't correct
24 Halted 0 ms 0 KB -