Submission #833840

#	Time	Username	Problem	Language	Result	Execution time	Memory
833840		pomuchle	Horses (IOI15_horses)	C++17	17 / 100	47 ms	54004 KiB

horses

#include "horses.h"
#include <cassert>
#include <vector>
#include <ios>
#define REP(i, n) for (int i=0; i<(n); ++i)
#define FOR(i, p, n) for (int i=(p); i<=(n); ++i)
#define V std::vector
typedef V <int> vi;
typedef long long ll;
typedef V <ll> vll;
#define CAP (ll(1e9+5))
#define MOD 1'000'000'007
struct stilnode{
    ll m,c; // modulo i z capem
    stilnode(){
        m=c=0;
    }
    stilnode(int i){
        m=c=i;
    }
    stilnode(ll nm, ll nc){
        m=nm,c=nc;
    }
    stilnode operator^(const stilnode &i) const{
        return {m*i.m%MOD, std::min(c*i.c, CAP)};
    }
};
struct stiltype{
    V <stilnode> t;
    int comp;
    stiltype(){}
    stiltype(int n, int X[]){
        for (comp=1; comp<n; comp<<=1);
        t.resize(comp<<1);
        --comp;
        REP(i, n)
            t[i+comp+1]=X[i];
        for (int i=comp; i; --i)
            t[i]=t[i<<1]^t[(i<<1)+1];
    }
    void wst(int i, int w){
        t[i+=comp]=w;
        for (i>>=1; i; i>>=1)
            t[i]=t[i<<1]^t[(i<<1)+1];
    }
    stilnode zap(int p, int k){
        stilnode r={1, 1};
        for (p+=comp,k+=comp+1; p<k; p>>=1,k>>=1){
            if (p&1)
                r=r^t[p++];
            if (k&1)
                r=r^t[--k];
        }
        return r;
    }
} stil;
struct stmintype{
    vi t;
    vi Y;
    int comp;
    int lacz(int i, int j){
        if (!i||!j)
            return i+j;
        if (i>j)
            std::swap(i, j);
        ll lew=Y[i],praw=Y[j]*stil.zap(i+1, j).c;
        return lew>=praw ? i : j;
    }
    stmintype(){}
    stmintype(int n, int v[]){ // translacja v!!!
        for (comp=1; comp<n; comp<<=1);
        t.resize(comp<<1);
        Y.resize(n+1);
        --comp;
        REP(i, n)
            Y[i+1]=v[i];
        FOR(i, 1, n)
            t[i+comp]=i;
        for (int i=comp; i; --i)
            t[i]=lacz(t[i<<1], t[(i<<1)+1]);
    }
    void wst(int i, int w=0){
        if (w) // w=0 -> noop
            Y[i]=w;
        for (i+=comp,i>>=1; i; i>>=1)
            t[i]=lacz(t[i<<1], t[(i<<1)+1]);
    }
} stmin;

int n;
int wynbru(){
    ll l=1,w=0;
    for (int i=1; i<=n; ++i){
        l*=stil.t[i+stil.comp].m;
        w=std::max(w, l*stmin.Y[i]);
    }
    return int(w%MOD);
}
int wyn(){
    int wpos=stmin.t[1];
    ll w=stil.zap(1, wpos).m*stmin.Y[wpos]%MOD;
    assert(w==wynbru());
#ifdef LOCAL
    printf("%lld\n", w);
#endif
    return int(w);
}

int init(int N, int X[], int Y[]) {
    n=N;
    stil=stiltype(N, X);
    stmin=stmintype(N, Y);
	return wyn();
}

int updateX(int pos, int val) {	
    ++pos;
    stil.wst(pos, val);
    stmin.wst(pos);
	return wyn();
}

int updateY(int pos, int val) {
    ++pos;
    stmin.wst(pos, val);
	return wyn();
}

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