Submission #1279423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279423		swishy123	Horses (IOI15_horses)	C++20	20 / 100	653 ms	32692 KiB

horses

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>

#define ll long long
using namespace std;

const int def = 5e5+1;
const ll mod = 1e9+7;

ll powmod(ll a, ll b){
    if (b == 0)
        return 1;
    if (b % 2 == 0){
        ll val = powmod(a, b / 2);
        return (val * val) % mod;
    }
    else
        return (a * powmod(a, b - 1)) % mod;
}
ll inv(ll x){
    return powmod(x, mod - 2);
}

ll bit[def];
void apply(int u, ll val){
    for (int i = u; i < def; i += i & -i)
        (bit[i] *= val) %= mod; 
}
ll query(int u){
    ll res = 1;
    for (int i = u; i > 0; i -= i & -i)
        (res *= bit[i]) %= mod;
    return res;
}

struct SegmentTree{
    vector<int> st;
    int n;

    SegmentTree(int n) : n(n){
        st = vector<int>(4 * n, 0);
    }
    void update(int l, int r, int crr, int i, int v){
        if (l > i || r < i)
            return;
        if (l == r){
            st[crr] = v;
            return;
        }
        int mid = (l + r) / 2;
        update(l, mid, crr * 2 + 1, i, v);
        update(mid + 1, r, crr * 2 + 2, i, v);

        st[crr] = max(st[crr * 2 + 1], st[crr * 2 + 2]);
    }
    int get(int l, int r, int ql, int qr, int crr){
        if (qr < l || qr > r)
            return 0;
        if (l >= ql && r <= qr)
            return st[crr];
        int mid = (l + r) / 2;
        return max(get(l, mid, ql, qr, crr * 2 + 1), get(mid + 1, r, qr, qr, crr * 2 + 2)); 
    }
};

SegmentTree st1(def);
SegmentTree st2(def);

ll x[def], y[def];
int n;

int get(){
    int l = n;
    __int128_t crr = 1;

    vector<int> pos;
    while (l > 0){
        int nxt = st1.get(0, def - 1, 0, l - 1, 0);
        if (nxt == 0){
            pos.push_back(0);
            break;
        }
        if (crr * x[nxt - 1] > 1e18){
            if (nxt != l)
                pos.push_back(nxt);
            break;
        }
        pos.push_back(nxt - 1);
        crr *= x[nxt - 1];
        l = nxt - 1;
    }
    
    ll prefix = query(l);
    __int128_t best = 1;

    crr = 1;
    reverse(pos.begin(), pos.end());
    
    for (int i = 0; i < pos.size(); i++){
        crr *= x[pos[i]];
        int nxt = n;

        if (i + 1 < pos.size())
            nxt = pos[i + 1];

        ll maxy = st2.get(0, def - 1, pos[i], nxt - 1, 0);
        best = max(best, crr * maxy);
    }
    
    best %= mod;
    ll res = (prefix * best) % mod;
    return res;
}

int init(int N, int X[], int Y[]){
    n = N;
    for (int i = 0; i < def; i++)
        bit[i] = 1;
    for (int i = 0; i < n; i++){
        x[i] = X[i];
        if (x[i] > 1)
            st1.update(0, def - 1, 0, i, i + 1);
        apply(i + 1, x[i]);
        y[i] = Y[i];
        st2.update(0, def - 1, 0, i, y[i]);
    }
    return get();
}

int updateX(int pos, int val){	
    apply(pos + 1, ((ll)inv(x[pos]) * (ll)val) % mod);
    x[pos] = val;

    if (x[pos] > 1)
        st1.update(0, def - 1, 0, pos, pos + 1);
    else
        st1.update(0, def - 1, 0, pos, 0);
	return get();
}

int updateY(int pos, int val){
    y[pos] = val;
    st2.update(0, def - 1, 0, pos, y[pos]);
	return get();
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23