oj.uz

Submission #153978

# Submission time Handle Problem Language Result Execution time Memory
153978 2019-09-17T16:00:43 Z pit4h Horses (IOI15_horses) C++14
17 / 100
 295 ms 43932 KB 
#include<bits/stdc++.h>
#include "horses.h"
#define ll long long
using namespace std;
const int mod = 1e9+7, base = (1<<20), N = 5e5+1;
ll tree[2*base+1], push[2*base+1], x[N], y[N];
ll fastpow(ll a, ll b) {
    if(b==0) {
        return 1;
    }
    ll c = fastpow(a, b/2);
    if(b%2==0) {
        return (c*c)%mod;
    }
    else {
        return ((c*c)%mod*a)%mod;
    }
}
ll inv(ll num) {
    return fastpow(num, mod-2);
}
void PUSH(int id, ll val) {
    tree[id]=(tree[id]*val)%mod;
    push[id]=(push[id]*val)%mod;
}
ll multiply(int id, int L, int R, int l, int r, ll val) {
    if(L>r || R<r) {
        return tree[id];
    }
    if(l<=L && r>=R) {
        tree[id]*=val;
        push[id]*=val;
        tree[id]%=mod;
        return tree[id];
    }
    PUSH(id*2, push[id]);
    PUSH(id*2+1, push[id]);
    push[id]=1;
    int M = (L+R)/2;
    tree[id]=max(multiply(id*2, L, M, l, r, val), multiply(id*2+1, M+1, R, l, r, val));
    return tree[id];
}
int init(int n, int X[], int Y[]) {
    for(int i=0; i<n; ++i) {
        x[i]=X[i];
        y[i]=Y[i];
    }
    for(int i=1; i<2*base; ++i) {
        push[i]=1;
    }
    tree[base]=(x[0]*y[0])%mod;
    for(int i=1; i<n; ++i) {
        tree[i+base]=(((tree[i+base-1]*x[i])%mod)*inv(y[i-1])%mod*y[i])%mod;
    }
    for(int i=base-1; i>=1; --i) {
        tree[i]=max(tree[i*2], tree[i*2+1]);
    }
	return (int)tree[1];
}
int updateX(int pos, int val) {
    multiply(1, 0, base-1, pos, base-1, (inv(x[pos]) * (ll)val)%mod);
    x[pos]=val;
	return (int)tree[1];
}
int updateY(int pos, int val) {
    multiply(1, 0, base-1, pos, pos, (inv(y[pos])*(ll)val)%mod);
    y[pos]=val;
	return (int)tree[1];
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24952 KB Output is correct
2 Correct 26 ms 24968 KB Output is correct
3 Correct 26 ms 24952 KB Output is correct
4 Correct 26 ms 24952 KB Output is correct
5 Correct 26 ms 24952 KB Output is correct
6 Correct 104 ms 24952 KB Output is correct
7 Correct 26 ms 24952 KB Output is correct
8 Correct 26 ms 24952 KB Output is correct
9 Correct 26 ms 24976 KB Output is correct
10 Correct 26 ms 24952 KB Output is correct
11 Correct 26 ms 24936 KB Output is correct
12 Correct 26 ms 24952 KB Output is correct
13 Correct 26 ms 24952 KB Output is correct
14 Correct 26 ms 24952 KB Output is correct
15 Correct 26 ms 24952 KB Output is correct
16 Correct 26 ms 24952 KB Output is correct
17 Correct 26 ms 24920 KB Output is correct
18 Correct 26 ms 24952 KB Output is correct
19 Correct 25 ms 24956 KB Output is correct
20 Correct 28 ms 24960 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24952 KB Output is correct
2 Correct 26 ms 24952 KB Output is correct
3 Correct 26 ms 24952 KB Output is correct
4 Correct 26 ms 24936 KB Output is correct
5 Correct 26 ms 24952 KB Output is correct
6 Correct 26 ms 24952 KB Output is correct
7 Correct 46 ms 24952 KB Output is correct
8 Correct 24 ms 24952 KB Output is correct
9 Correct 26 ms 24952 KB Output is correct
10 Correct 25 ms 24952 KB Output is correct
11 Correct 30 ms 24952 KB Output is correct
12 Correct 31 ms 24924 KB Output is correct
13 Correct 26 ms 24952 KB Output is correct
14 Correct 26 ms 24952 KB Output is correct
15 Correct 35 ms 24952 KB Output is correct
16 Correct 26 ms 24952 KB Output is correct
17 Correct 30 ms 24924 KB Output is correct
18 Correct 26 ms 24952 KB Output is correct
19 Correct 26 ms 24968 KB Output is correct
20 Correct 26 ms 24952 KB Output is correct
21 Incorrect 27 ms 24952 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 25000 KB Output is correct
2 Correct 26 ms 24952 KB Output is correct
3 Correct 26 ms 24952 KB Output is correct
4 Correct 27 ms 24952 KB Output is correct
5 Correct 26 ms 25016 KB Output is correct
6 Correct 26 ms 24952 KB Output is correct
7 Correct 27 ms 24952 KB Output is correct
8 Correct 26 ms 24952 KB Output is correct
9 Correct 33 ms 25080 KB Output is correct
10 Correct 27 ms 25012 KB Output is correct
11 Correct 27 ms 24952 KB Output is correct
12 Correct 26 ms 24952 KB Output is correct
13 Correct 27 ms 25080 KB Output is correct
14 Correct 27 ms 25080 KB Output is correct
15 Correct 30 ms 24952 KB Output is correct
16 Correct 26 ms 24952 KB Output is correct
17 Correct 25 ms 24952 KB Output is correct
18 Correct 26 ms 24952 KB Output is correct
19 Correct 26 ms 24980 KB Output is correct
20 Correct 26 ms 24952 KB Output is correct
21 Incorrect 26 ms 24956 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24956 KB Output is correct
2 Correct 26 ms 24952 KB Output is correct
3 Correct 26 ms 24952 KB Output is correct
4 Correct 26 ms 24952 KB Output is correct
5 Correct 26 ms 24952 KB Output is correct
6 Correct 26 ms 24952 KB Output is correct
7 Correct 26 ms 24952 KB Output is correct
8 Correct 26 ms 24952 KB Output is correct
9 Correct 26 ms 24952 KB Output is correct
10 Correct 26 ms 24952 KB Output is correct
11 Correct 26 ms 24952 KB Output is correct
12 Correct 26 ms 24952 KB Output is correct
13 Correct 31 ms 24952 KB Output is correct
14 Correct 27 ms 24952 KB Output is correct
15 Correct 26 ms 24952 KB Output is correct
16 Correct 24 ms 24952 KB Output is correct
17 Correct 26 ms 25080 KB Output is correct
18 Correct 26 ms 24956 KB Output is correct
19 Correct 26 ms 24952 KB Output is correct
20 Correct 27 ms 24952 KB Output is correct
21 Incorrect 26 ms 24956 KB Output isn't correct
22 Halted 0 ms 0 KB -