Submission #614000

#	Time	Username	Problem	Language	Result	Execution time	Memory
614000		Lucpp	Horses (IOI15_horses)	C++17	100 / 100	730 ms	65608 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;

template<typename T>
struct SegTree{
	virtual T combine(T t1, T t2) = 0;
	virtual T id() = 0;

	int cap;
	vector<T> seg;
	void build(const vector<T>& v){
		int n = (int)v.size();
		for(cap=1; cap < n; cap*=2);
		seg.assign(2*cap, id());
		for(int i = 0; i < n; i++) seg[i+cap] = v[i];
		for(int i = cap-1; i >= 1; i--) seg[i] = combine(seg[2*i], seg[2*i+1]);
	}
	void upd(int i, T v){
		i += cap;
		seg[i] = v;
		while(i > 1){
			i /= 2;
			seg[i] = combine(seg[2*i], seg[2*i+1]);
		}
	}
	T qry(int l, int r, int a, int b, int i){
		if(l <= a && b <= r) return seg[i];
		if(b < l || r < a) return id();
		int m = (a+b)/2;
		return combine(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
	}
	T qry(int l, int r){return qry(l, r, 1, cap, 1);}
};

struct ProdTree : SegTree<ll> {
	ll combine(ll t1, ll t2) override {return (t1*t2)%MOD;}
	ll id() override {return 1;}
};
struct MaxTree : SegTree<ll> {
	ll combine(ll t1, ll t2) override {return max(t1, t2);}
	ll id() override {return 0;}
};

vector<ll> x, y;
set<int> non1;
int n;
ProdTree p;
MaxTree m;

int calc(){
	ll prod = 1;
	auto it = non1.rbegin();
	for(; it != non1.rend() && prod < MOD; it++){
		prod *= x[*it];
	}
	int last = -1;
	if(prod >= MOD) last = *(--it);
	ll pref = p.qry(1, last+1);
	prod = 1;
	ll best = 0;
	while(it != non1.rbegin()){
		it--;
		best = max(best, prod*m.qry(last+1, *it));
		prod *= x[*it];
		last = *it;
	}
	best = max(best, prod*m.qry(last+1, n));
	return int(((best%MOD)*pref)%MOD);
}

int init(int N, int X[], int Y[]){
	n = N;
	x.resize(n);
	y.resize(n);
	for(int i = 0; i < n; i++){
		x[i] = X[i], y[i] = Y[i];
		if(x[i] != 1) non1.insert(i);
	}
	p.build(x);
	m.build(y);
	return calc();
}

int updateX(int pos, int val) {
	x[pos] = val;
	p.upd(pos, val);
	if(val == 1) non1.erase(pos);
	else non1.insert(pos);
	return calc();
}

int updateY(int pos, int val) {
	y[pos] = val;
	m.upd(pos, val);
	return calc();
}

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