oj.uz

Submission #833792

# Submission time Handle Problem Language Result Execution time Memory
833792 2023-08-22T08:39:35 Z pomuchle Horses (IOI15_horses) C++17
0 / 100
 66 ms 29300 KB 
#include "horses.h"
#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 1000000007
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];
        REP(i, n)
            t[i+comp+1]=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 wyn(){
    int wpos=stmin.t[1];
    ll w=stil.zap(1, wpos).m*stmin.Y[wpos]%MOD;
#ifdef LOCAL
    printf("%lld\n", w);
#endif
    return int(w);
}

int init(int N, int X[], int Y[]) {
    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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 29300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -