Submission #1257784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257784		gustavo_d	말 (IOI15_horses)	C++17	17 / 100	570 ms	29932 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1e9+7;
const ll INF = 1e18;
const int LOG = 35;

struct Node {
	ll prodX, mxX, mxY;

	Node(ll _prodX=1, ll _mxX=-INF, ll _mxY=-INF):
		prodX(_prodX), mxX(_mxX), mxY(_mxY) {}
	Node operator+(Node right) {
		Node left = *this;
		return Node(
			(left.prodX * right.prodX) % MOD,
			max(left.mxX, right.mxX),
			max(left.mxY, right.mxY)
		);
	}
};

struct SEG {
	vector<Node> seg; int n;

	SEG(int _n=0) {
		n = 1;
		while (n < _n) n <<= 1;
		seg = vector<Node> (2*n);
	}

	int getLeft(int v) {
		return 2*v;
	}

	int getRight(int v) {
		return 2*v+1;
	}

	void upd(int v, int l, int r, int i, Node val) {
		if (l == r) {
			seg[v] = val;
			return;
		}
		int m = (l + r) / 2;
		if (i <= m) upd(getLeft(v), l, m, i, val);
		else upd(getRight(v), m+1, r, i, val);
		seg[v] = seg[getLeft(v)] + seg[getRight(v)];
	}

	Node rng(int v, int l, int r, int a, int b) {
		if (a <= l and r <= b) {
			return seg[v];
		}
		if (r < a or b < l) return Node();
		int m = (l + r) / 2;
		return rng(getLeft(v), l, m, a, b) + rng(getRight(v), m+1, r, a, b);
	}
};

int n;
SEG seg;

int getAns() {
	ll mxY = 0, mxProdX = 0; int ans = 0;
	for (int i=1; i<=min(LOG, n) and mxProdX * mxY <= INF; i++) {
		Node node = seg.rng(1, 0, seg.n-1, n-i, n-i);
		ll x = node.mxX, y = node.mxY;
		if (mxProdX * mxY < y) {
			mxY = y;
			mxProdX = 1;
			ans = n-i;
		}
		mxProdX *= x;
	}
	return (int)((seg.rng(1, 0, seg.n-1, 0, ans).prodX * mxY) % MOD);
}

int init(int N, int X[], int Y[]) {
	n = N;
	seg = SEG(n);
	for (int i=0; i<n; i++)
		seg.upd(1, 0, seg.n-1, i, Node(X[i], X[i], Y[i]));
	return getAns();
}

int updateX(int pos, int val) {
	Node curr = seg.rng(1, 0, seg.n-1, pos, pos);
	curr.mxX = val; curr.prodX = val;
	seg.upd(1, 0, seg.n-1, pos, curr);
	return getAns();
}

int updateY(int pos, int val) {
	Node curr = seg.rng(1, 0, seg.n-1, pos, pos);
	curr.mxY = val;
	seg.upd(1, 0, seg.n-1, pos, curr);
	return getAns();
}

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