Submission #302246

#	Time	Username	Problem	Language	Result	Execution time	Memory
302246		square1001	Horses (IOI15_horses)	C++14	100 / 100	690 ms	53496 KiB

horses

#include "horses.h"
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
class segment_tree_1 {
private:
	int sz;
	vector<int> val;
	int range_mul(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l) return 1;
		if(a <= l && r <= b) return val[k];
		int lc = range_mul(a, b, k * 2, l, (l + r) >> 1);
		int rc = range_mul(a, b, k * 2 + 1, (l + r) >> 1, r);
		return int(1LL * lc * rc % mod);
	}
public:
	segment_tree_1() : sz(0), val() {};
	segment_tree_1(int N) {
		sz = 1;
		while(sz < N) sz *= 2;
		val = vector<int>(sz * 2, 1);
	}
	void update(int pos, int x) {
		pos += sz;
		val[pos] = x;
		while(pos > 1) {
			pos >>= 1;
			val[pos] = int(1LL * val[pos * 2] * val[pos * 2 + 1] % mod);
		}
	}
	int range_mul(int l, int r) {
		return range_mul(l, r, 1, 0, sz);
	}
};
class segment_tree_2 {
private:
	int sz;
	vector<int> val;
	int range_max(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l) return 1;
		if(a <= l && r <= b) return val[k];
		int lc = range_max(a, b, k * 2, l, (l + r) >> 1);
		int rc = range_max(a, b, k * 2 + 1, (l + r) >> 1, r);
		return max(lc, rc);
	}
public:
	segment_tree_2() : sz(0), val() {};
	segment_tree_2(int N) {
		sz = 1;
		while(sz < N) sz *= 2;
		val = vector<int>(sz * 2, 0);
	}
	void update(int pos, int x) {
		pos += sz;
		val[pos] = x;
		while(pos > 1) {
			pos >>= 1;
			val[pos] = max(val[pos * 2], val[pos * 2 + 1]);
		}
	}
	int range_max(int l, int r) {
		return range_max(l, r, 1, 0, sz);
	}
};
int N; set<int> s; vector<int> X, Y;
segment_tree_1 seg1;
segment_tree_2 seg2;
int solve() {
	long long mult = 1;
	set<int>::iterator it = s.end();
	vector<int> st = { N };
	while(it != s.begin()) {
		--it;
		mult *= X[*it];
		st.push_back(*it);
		if(mult > 1000000000) break;
	}
	if(mult <= 1000000000 && st.back() != 0) {
		st.push_back(0);
	}
	reverse(st.begin(), st.end());
	int ini = st[0];
	int coeff = seg1.range_mul(0, ini + 1);
	long long ans = 0;
	mult = 1;
	for(int i = 0; i < int(st.size()) - 1; ++i) {
		int mx = seg2.range_max(st[i], st[i + 1]);
		ans = max(ans, mult * mx);
		if(i != int(st.size()) - 2) {
			mult *= X[st[i + 1]];
		}
	}
	ans = (ans % mod) * coeff % mod;
	return int(ans);
}
int init(int N_, int X_[], int Y_[]) {
	N = N_;
	X = vector<int>(X_, X_ + N);
	Y = vector<int>(Y_, Y_ + N);
	seg1 = segment_tree_1(N);
	seg2 = segment_tree_2(N);
	for(int i = 0; i < N; ++i) {
		if(X[i] >= 2) {
			s.insert(i);
		}
		seg1.update(i, X[i]);
		seg2.update(i, Y[i]);
	}
	return solve();
}
int updateX(int pos, int val) {
	if(X[pos] == 1 && val >= 2) {
		s.insert(pos);
	}
	if(X[pos] >= 2 && val == 1) {
		s.erase(pos);
	}
	X[pos] = val;
	seg1.update(pos, val);
	return solve();
}
int updateY(int pos, int val) {
	Y[pos] = val;
	seg2.update(pos, val);
	return solve();
}

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