Submission #819778

#	Time	Username	Problem	Language	Result	Execution time	Memory
819778		josanneo22	Horses (IOI15_horses)	C++17	100 / 100	301 ms	91288 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const ll N = 5e5 + 500, mod = 1e9 + 7;
ll chen(ll x, ll y) { return ((x % mod) * (y % mod)) % mod; }
ll jia(ll x, ll y) { return ((x % mod) + (y % mod)) % mod; }
ll a[N], b[N];
struct yl {
    ll l, r, pro, ans;
    ld sumlog, mx;
}tr[N << 2];
void pushup(ll p) {
    ll l = p << 1, r = p << 1 | 1;
    tr[p].sumlog = tr[l].sumlog + tr[r].sumlog;
    tr[p].pro = chen(tr[l].pro, tr[r].pro);
    if (tr[l].mx < tr[l].sumlog + tr[r].mx) {
        tr[p].mx = tr[l].sumlog + tr[r].mx;
        tr[p].ans = chen(tr[l].pro, tr[r].ans);
    }
    else {
        tr[p].mx = tr[l].mx;
        tr[p].ans = tr[l].ans;
    }
    return;
}
void build(ll p, ll l, ll r) {
    tr[p].l = l; tr[p].r = r;
    if (l == r) {
        tr[p].ans = chen(a[l], b[l]);
        tr[p].pro = a[l] % mod;
        tr[p].sumlog = log(a[l]);
        tr[p].mx = log(a[l] * b[l]);
        return;
    }
    ll mid = (l + r) >> 1;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
    pushup(p);
    return;
}
void modify(ll p, ll l) {
    if (tr[p].l == tr[p].r) {
        tr[p].ans = chen(a[l], b[l]);
        tr[p].pro = a[l] % mod;
        tr[p].sumlog = log(a[l]);
        tr[p].mx = log(a[l] * b[l]);
        return;
    }
    ll mid = (tr[p].l + tr[p].r) >> 1;
    if (l <= mid) modify(p << 1, l);
    if (l > mid) modify(p << 1 | 1, l);
    pushup(p);
    return;
}

int init(int n, int X[], int Y[]) {
    for (int i = 1; i <= n; i++) a[i] = X[i - 1];
    for (int i = 1; i <= n; i++) b[i] = Y[i - 1];
    build(1, 1, n);
    return (int)tr[1].ans;
}
int updateX(int pos, int val) {
    pos++;
    a[pos] = (ll)val; modify(1, pos);
    return (int)tr[1].ans;
}
int updateY(int pos, int val) {
    pos++;
    b[pos] = (ll)val; modify(1, pos);
    return (int)tr[1].ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23