Submission #1049511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049511		dpsaveslives	Horses (IOI15_horses)	C++17	100 / 100	88 ms	55900 KiB

horses

#include <bits/stdc++.h>
#define ll long long
#define d double
using namespace std;
const int MAXN = 5e5+1;
const ll 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*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 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23