Submission #302227

#	Time	Username	Problem	Language	Result	Execution time	Memory
302227		square1001	Horses (IOI15_horses)	C++14	17 / 100	1570 ms	10348 KiB

horses

#include "horses.h"
#include <queue>
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
int N; priority_queue<int> que; vector<int> X, Y;
int solve() {
	long long mult = 1;
	vector<int> st = { N };
	while(!que.empty()) {
		int u = -1;
		while(!que.empty()) {
			u = que.top(); que.pop();
			if(que.empty() || u != que.top()) break;
		}
		mult *= X[u];
		if(X[u] >= 2) {
			st.push_back(u);
		}
		if(mult > 1000000000) break;
	}
	bool flag = false;
	if(mult <= 1000000000 && st.back() != 0) {
		st.push_back(0);
		flag = true;
	}
	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]];
		}
		if(i != 0 || flag) {
			que.push(st[i]);
		}
	}
	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) {
			que.push(i);
		}
	}
	return solve();
}
int updateX(int pos, int val) {
	X[pos] = val;
	if(X[pos] >= 2) {
		que.push(pos);
	}
	return solve();
}
int updateY(int pos, int val) {
	Y[pos] = val;
	return solve();
}

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