제출 #819769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
819769		josanneo22	말 (IOI15_horses)	C++17	0 / 100	91 ms	58388 KiB

horses

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

int updateX(int pos, int val) {	
	b[pos+1]=val; modify(1,pos+1);
	return tr[1].ans;
}

int updateY(int pos, int val) {
	a[pos+1]=val; modify(1,pos+1);
	return tr[1].ans;
}

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