oj.uz

Submission #1099215

# Submission time Handle Problem Language Result Execution time Memory
1099215 2024-10-10T19:32:55 Z Tymond Horses (IOI15_horses) C++17
37 / 100
 837 ms 68692 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 x0 * ... * xa
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};
        ok.erase(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 10 ms 20828 KB Output is correct
3 Correct 10 ms 20756 KB Output is correct
4 Correct 10 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 20748 KB Output is correct
9 Correct 9 ms 20828 KB Output is correct
10 Correct 9 ms 20828 KB Output is correct
11 Correct 9 ms 20828 KB Output is correct
12 Correct 11 ms 20824 KB Output is correct
13 Correct 9 ms 20828 KB Output is correct
14 Correct 10 ms 20824 KB Output is correct
15 Correct 9 ms 20824 KB Output is correct
16 Correct 9 ms 20828 KB Output is correct
17 Correct 9 ms 20828 KB Output is correct
18 Correct 9 ms 20816 KB Output is correct
19 Correct 9 ms 20828 KB Output is correct
20 Correct 13 ms 20756 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20824 KB Output is correct
2 Correct 9 ms 20824 KB Output is correct
3 Correct 11 ms 20828 KB Output is correct
4 Correct 11 ms 20840 KB Output is correct
5 Correct 9 ms 20824 KB Output is correct
6 Correct 11 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 11 ms 20832 KB Output is correct
10 Correct 10 ms 20976 KB Output is correct
11 Correct 11 ms 20828 KB Output is correct
12 Correct 11 ms 20828 KB Output is correct
13 Correct 9 ms 20828 KB Output is correct
14 Correct 9 ms 20820 KB Output is correct
15 Correct 9 ms 20828 KB Output is correct
16 Correct 13 ms 20824 KB Output is correct
17 Correct 10 ms 20828 KB Output is correct
18 Correct 11 ms 20824 KB Output is correct
19 Correct 11 ms 20852 KB Output is correct
20 Correct 11 ms 20828 KB Output is correct
21 Correct 11 ms 20992 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 656 ms 60756 KB Output is correct
2 Correct 837 ms 68692 KB Output is correct
3 Correct 744 ms 60756 KB Output is correct
4 Correct 786 ms 64312 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 20988 KB Output is correct
3 Correct 8 ms 20828 KB Output is correct
4 Correct 8 ms 20828 KB Output is correct
5 Correct 9 ms 20960 KB Output is correct
6 Correct 9 ms 20988 KB Output is correct
7 Correct 9 ms 20824 KB Output is correct
8 Correct 9 ms 20824 KB Output is correct
9 Correct 9 ms 20828 KB Output is correct
10 Correct 9 ms 20828 KB Output is correct
11 Correct 10 ms 20980 KB Output is correct
12 Correct 9 ms 20828 KB Output is correct
13 Correct 9 ms 20832 KB Output is correct
14 Correct 9 ms 20752 KB Output is correct
15 Correct 11 ms 20824 KB Output is correct
16 Correct 10 ms 20828 KB Output is correct
17 Correct 10 ms 20864 KB Output is correct
18 Correct 9 ms 20932 KB Output is correct
19 Correct 9 ms 20824 KB Output is correct
20 Correct 11 ms 20828 KB Output is correct
21 Correct 11 ms 20828 KB Output is correct
22 Correct 11 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 9 ms 20828 KB Output is correct
3 Correct 9 ms 20824 KB Output is correct
4 Correct 9 ms 20828 KB Output is correct
5 Correct 15 ms 20828 KB Output is correct
6 Correct 9 ms 20828 KB Output is correct
7 Correct 9 ms 20828 KB Output is correct
8 Correct 11 ms 21080 KB Output is correct
9 Correct 9 ms 20828 KB Output is correct
10 Correct 9 ms 20936 KB Output is correct
11 Correct 9 ms 20824 KB Output is correct
12 Correct 11 ms 20868 KB Output is correct
13 Correct 9 ms 20780 KB Output is correct
14 Correct 10 ms 20828 KB Output is correct
15 Correct 11 ms 20824 KB Output is correct
16 Correct 10 ms 20828 KB Output is correct
17 Correct 10 ms 20876 KB Output is correct
18 Correct 10 ms 20912 KB Output is correct
19 Correct 10 ms 20816 KB Output is correct
20 Correct 10 ms 20976 KB Output is correct
21 Correct 11 ms 20936 KB Output is correct
22 Correct 9 ms 20792 KB Output is correct
23 Incorrect 17 ms 20828 KB Output isn't correct
24 Halted 0 ms 0 KB -