oj.uz

Submission #833840

# Submission time Handle Problem Language Result Execution time Memory
833840 2023-08-22T08:56:51 Z pomuchle Horses (IOI15_horses) C++17
17 / 100
 47 ms 54004 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Runtime error 1 ms 340 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 54004 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Runtime error 1 ms 340 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 284 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Runtime error 1 ms 340 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -