Submission #1257800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257800		gustavo_d	Horses (IOI15_horses)	C++17	100 / 100	1211 ms	38152 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; int posMxY;

	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; vector<tuple<int, int, int>> rngs;

	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);
	}

	void saveRngs(int v, int l, int r, int a, int b) {
		if (a <= l and r <= b) {
			rngs.emplace_back(v, l, r);
			return;
		}
		if (r < a or b < l) return;
		int m = (l + r) / 2;
		saveRngs(getRight(v), m+1, r, a, b);
		saveRngs(getLeft(v), l, m, a, b);
	}

	int nxt(int v, int l, int r) {
		if (l == r) return l;
		int m = (l + r) / 2;
		if (seg[getRight(v)].mxX >= 2) return nxt(getRight(v), m+1, r);
		else return nxt(getLeft(v), l, m);
	}

	int nxt(int x) {
		// primeiro X[i] >= 2
		int res = 0;
		saveRngs(1, 0, n-1, 0, x);

		for (auto [v, l, r] : rngs) {
			if (seg[v].mxX == 1) continue;
			res = nxt(v, l, r);
			break;
		}

		rngs.clear();

		return res;
	}
};

int n;
SEG seg;

int getAns() {
	ll mxY = 0, mxProdX = 0; int ans = 0;
	for (int i=1, pos = n-1; i<=min(LOG, n) and mxProdX * mxY <= 1000000000LL and pos >= 0; i++) {
		int newPos = seg.nxt(pos);
		Node node = seg.rng(1, 0, seg.n-1, newPos, newPos);
		Node rng = seg.rng(1, 0, seg.n-1, newPos, pos);
		ll x = node.mxX, y = rng.mxY;
		if (mxProdX * mxY < y) {
			mxY = y;
			mxProdX = 1;
			ans = newPos;
		}
		mxProdX *= x;
		// cout << newPos << ' ' << x << ' ' << y << endl;
		pos = newPos - 1;
	}
	// cout << endl;
	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: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23