제출 #1135446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135446		gyg	말 (IOI15_horses)	C++20	37 / 100	71 ms	21320 KiB

horses

// 0 indexed btw

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define lint long long
#define arr array 
const int N = 5e5 + 5;
const lint MD = 1e9 + 7;

int n;
arr<lint, N> grw, prc;

lint md(lint x) { return (x + MD) % MD; }

struct Sg {
	arr<lint, 5 * N> sg;
	void bld(int u = 1, int lw = 1, int hg = n) {
		if (lw == hg) { sg[u] = grw[lw]; return; }
		int mdl = (lw + hg) / 2;
		bld(2 * u, lw, mdl), bld(2 * u + 1, mdl + 1, hg);
		sg[u] = md(sg[2 * u] * sg[2 * u + 1]);
	}
	void upd(int i, lint x, int u = 1, int lw = 1, int hg = n) {
		if (i < lw || hg < i) return;
		if (lw == hg) { sg[u] = x; return; }
		int mdl = (lw + hg) / 2;
		upd(i, x, 2 * u, lw, mdl), upd(i, x, 2 * u + 1, mdl + 1, hg);
		sg[u] = md(sg[2 * u] * sg[2 * u + 1]);
	}
	lint qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
		if (r < lw || hg < l) return 1;
		if (l <= lw && hg <= r) return sg[u];
		int mdl = (lw + hg) / 2;
		return md(qry(l, r, 2 * u, lw, mdl) * qry(l, r, 2 * u + 1, mdl + 1, hg));
	}
} sg;

lint slv() {
	int bst = max(n - 33, 1);
	lint grw_prd = 1;
	for (int i = max(n - 32, 2); i <= n; i++) {
		grw_prd *= grw[i];
		if (grw_prd > prc[bst] || grw_prd * prc[i] > prc[bst]) {
			bst = i;
			grw_prd = 1;
		}
	}

	lint ans = md(sg.qry(1, bst) * prc[bst]);
	return ans;
}

int init(int _n, int _grw[], int _prc[]) {
	n = _n;
	for (int i = 1; i <= n; i++) grw[i] = _grw[i - 1], prc[i] = _prc[i - 1];
	sg.bld();
	return slv();
}

int updateX(int id, int vl) {	
	id++, grw[id] = vl;
	sg.upd(id, vl);
	return slv();
}

int updateY(int id, int vl) {
	id++, prc[id] = vl;
	return slv();
}

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