oj.uz

Submission #1049502

# Submission time Handle Problem Language Result Execution time Memory
1049502 2024-08-08T19:45:51 Z dpsaveslives Horses (IOI15_horses) C++17
17 / 100
 89 ms 55636 KB 
#include <bits/stdc++.h>
#define ll long long
#define d double
using namespace std;
const int MAXN = 5e5+1;
const int MOD = 1e9+7;
int x[MAXN], y[MAXN], n;
struct node{
    d mx, sum;
    ll res, mult;
}tree[MAXN<<2];
void pushup(int p){
    tree[p].sum = tree[p<<1].sum+tree[(p<<1)|1].sum;
    tree[p].mx = max(tree[p<<1].mx,tree[p<<1].sum+tree[(p<<1)|1].mx);
    tree[p].mult = tree[p<<1].mult%MOD*tree[(p<<1)|1].mult%MOD;
    if(tree[p<<1].mx >= tree[p<<1].sum+tree[(p<<1)|1].mx){
        tree[p].res = tree[p<<1].res;
    }
    else{
        tree[p].res = tree[(p<<1)|1].res%MOD*tree[p<<1].mult%MOD;
    }
}
void build(int l, int r, int p){
    if(l == r){
        tree[p].sum = log(1.0*x[l]);
        tree[p].mx = log(1.0*x[l]*y[l]);
        tree[p].mult = x[l]%MOD;
        tree[p].res = x[l]%MOD*y[l]%MOD;
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,(p<<1)); build(mid+1,r,(p<<1)|1);
    pushup(p);
}
void upd(int tar, int l, int r, int p){
    if(l == r){
        tree[p].mx = log(1.0*x[tar]*y[tar]);
        tree[p].sum = log(1.0*x[tar]);
        tree[p].mult = x[tar]%MOD;
        tree[p].res = x[tar]%MOD*y[tar]%MOD;
        return;
    }
    int mid = (l+r)>>1;
    if(tar <= mid) upd(tar,l,mid,p<<1);
    else upd(tar,mid+1,r,(p<<1)|1);
    pushup(p);
}
ll init(int N, int X[], int Y[]){
    n = N;
    for(int i = 0;i<N;++i){
        x[i+1] = X[i];
        y[i+1] = Y[i];
    }
    build(1,N,1);
    return tree[1].res;
}
ll updateX(int pos, int val){
    x[pos+1] = val;
    upd(pos+1,1,n,1);
    return tree[1].res;
}
ll updateY(int pos, int val){
    y[pos+1] = val;
    upd(pos+1,1,n,1);
    return tree[1].res;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 46752 KB Output is correct
2 Incorrect 89 ms 55636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 0 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 0 ms 4544 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 0 ms 4444 KB Output is correct
11 Correct 0 ms 4444 KB Output is correct
12 Correct 0 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 0 ms 4536 KB Output is correct
15 Correct 0 ms 4444 KB Output is correct
16 Correct 0 ms 4444 KB Output is correct
17 Correct 0 ms 4444 KB Output is correct
18 Correct 0 ms 4444 KB Output is correct
19 Correct 0 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Incorrect 1 ms 4540 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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