Submission #1135795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135795		gyg	Horses (IOI15_horses)	C++20	37 / 100	104 ms	37724 KiB

horses

// 0 indexed btw

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define lint long long
#define arr array 
#define pli pair<lint, int>
#define fir first 
#define sec second
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 Prd_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));
	}
} prd_sg;

struct Mx_Sg {
	arr<pli, 5 * N> sg;
	void bld(int u = 1, int lw = 1, int hg = n) {
		if (lw == hg) { sg[u] = {prc[lw], lw}; return; }
		int md = (lw + hg) / 2;
		bld(2 * u, lw, md), bld(2 * u + 1, md + 1, hg);
		sg[u] = max(sg[2 * u], sg[2 * u + 1]);
	}
	void upd(int i, int x, int u = 1, int lw = 1, int hg = n) {
		if (i < lw || hg < i) return;
		if (lw == hg) { sg[u] = {x, lw}; return; }
		int md = (lw + hg) / 2;
		upd(i, x, 2 * u, lw, md), upd(i, x, 2 * u + 1, md + 1, hg);
		sg[u] = max(sg[2 * u], sg[2 * u + 1]);
	}
	pli qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
		if (r < lw || hg < l) return {-1, -1};
		if (l <= lw && hg <= r) return sg[u];
		int md = (lw + hg) / 2;
		return max(qry(l, r, 2 * u, lw, md), qry(l, r, 2 * u + 1, md + 1, hg));
	}
} mx_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(prd_sg.qry(1, bst) * mx_sg.qry(bst, bst).fir);
	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];
	prd_sg.bld(), mx_sg.bld();
	return slv();
}

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

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

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