Submission #1099215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099215		Tymond	Horses (IOI15_horses)	C++17	37 / 100	837 ms	68692 KiB

horses

#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 / 17
• Subtask 2: 0 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23