Submission #302235

#	Time	Username	Problem	Language	Result	Execution time	Memory
302235		square1001	Horses (IOI15_horses)	C++14	34 / 100	1582 ms	33912 KiB

horses

#include "horses.h"
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
int N; set<int> s; vector<int> X, Y;
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 = 1;
	for(int i = 0; i <= ini; ++i) {
		coeff = int(1LL * coeff * X[i] % mod);
	}
	long long ans = 0;
	mult = 1;
	for(int i = 0; i < int(st.size()) - 1; ++i) {
		int mx = 0;
		for(int j = st[i]; j < st[i + 1]; ++j) {
			mx = max(mx, Y[j]);
		}
		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);
	for(int i = 0; i < N; ++i) {
		if(X[i] >= 2) {
			s.insert(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;
	return solve();
}
int updateY(int pos, int val) {
	Y[pos] = val;
	return solve();
}

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