Submission #1225427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225427		Hamed_Ghaffari	Horses (IOI15_horses)	C++20	100 / 100	512 ms	36840 KiB

horses

#include <bits/stdc++.h>
using namespace std;

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 5e5+5, MOD = 1e9+7;

inline int power(int a, int b) {
    int res = 1;
    while(b) {
        if(b&1) res = 1ll*res*a%MOD;
        a = 1ll*a*a%MOD;
        b >>= 1;
    }
    return res;
}

int n, X[MXN], Y[MXN], tot, seg[MXN<<2];
void upd(int p, int l=0, int r=n, int id=1) {
    if(r-l == 1) {
        seg[id] = Y[p];
        return;
    }
    p<mid ? upd(p, l, mid, lc) : upd(p, mid, r, rc);
    seg[id] = max(seg[lc], seg[rc]);
}
int get(int s, int e, int l=0, int r=n, int id=1) {
    if(s>=r || l>=e) return 0;
    if(s<=l && r<=e) return seg[id];
    return max(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}

set<int> st;

inline int get() {
    int A=1, B=1, cur=1, tmp;
    if(st.empty()) A = seg[1];
    else {
        A = get(*st.rbegin(), n);
        auto it = prev(st.end());
        while(1) {
            if((*it)==0) break;
            if(1ll*cur*X[*it]>=MOD) break;
            cur *= X[*it];
            tmp = it==st.begin() ? get(0, *it) : get(*prev(it), *it);
            if(1ll*A*cur < 1ll*B*tmp)
                A = tmp, B = cur; 
            if(it==st.begin()) break;
            it = prev(it);
        }
    }
    return 1ll*tot*A%MOD*power(B, MOD-2)%MOD;
}

int init(int N, int X[], int Y[]) {
    n = N;
    tot = 1;
    for(int i=0; i<n; i++) {
        ::X[i] = X[i];
        ::Y[i] = Y[i];
        upd(i);
        if(X[i]>1) st.insert(i);
        tot = 1ll*tot*X[i]%MOD;
    }
    return get();
}

int updateX(int pos, int val) {
    st.erase(pos);
    tot = 1ll*tot*power(X[pos], MOD-2)%MOD;
    X[pos] = val;
    if(X[pos]>1) st.insert(pos);
    tot = 1ll*tot*val%MOD;
    return get();
}

int updateY(int pos, int val) {
    Y[pos] = val;
    upd(pos);
    return get();
}

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