Submission #588222

#	Time	Username	Problem	Language	Result	Execution time	Memory
588222		dnass	Horses (IOI15_horses)	C++17	100 / 100	1205 ms	73604 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef long double lf;
#define MOD 1000000007LL
#define INF 1000000000000000000LL

lld n;
vector<lld> x, y;
set<lld> big;

struct itemX{
	lld val;
	itemX(){
		val = 0;
	}
	itemX(lld valval){
		val=valval;
		val%=MOD;
	}
};

itemX merge(itemX a, itemX b){
	lld res = a.val*b.val; res%=MOD;
	return itemX(res);
}

itemX build_leaf(lld xxx){
	return itemX(xxx);
}

itemX X_NEUT = itemX(1);

struct STX{

	vector<itemX> st;

	void init(){
		lld sz = 1;
		while(sz<n) sz*=2;
		st.resize(2*sz);
	}

	void build(lld v = 1, lld tl = 0, lld tr = n-1){
		if(tl==tr) st[v] = build_leaf(x[tl]);
		else{
			lld tm = (tl+tr)/2;
			build(2*v, tl, tm);
			build(2*v+1,tm+1,tr);
			st[v] = merge(st[2*v], st[2*v+1]);
		}
	}

	itemX query(lld l, lld r, lld v = 1, lld tl=0, lld tr=n-1){
		if(l>r) return X_NEUT;
		if(l==tl&&r==tr) return st[v];
		lld tm = (tl+tr)/2;
		return merge(query(l,min(r,tm),2*v, tl, tm),query(max(l, tm+1), r, 2*v+1, tm+1,tr));
	}

	void upd(lld new_val, lld pos, lld v=1,lld tl=0, lld tr=n-1){
		if(tl==tr) st[v] = build_leaf(new_val);
		else{
			lld tm = (tl+tr)/2;
			if(pos<=tm) upd(new_val, pos, 2*v, tl, tm);
			else upd(new_val, pos, 2*v+1,tm+1,tr);
			st[v] = merge(st[2*v],st[2*v+1]);
		}
	}

};

struct itemY{
	lld val, ind;
	itemY(){
		val=-INF;
		ind = -1;
	}
	itemY(lld valval, lld indind){
		val=valval, ind=indind;
	}
};

itemY merge(itemY a, itemY b){
	return a.val>b.val?a:b;
}

itemY build_leaf(lld xxx, lld indind){
	return itemY(xxx,indind);
}

itemY Y_NEUT = itemY(-INF,-1);

struct STY{

	vector<itemY> st;

	void init(){
		lld sz = 1;
		while(sz<n) sz*=2;
		st.resize(2*sz);
	}

	void build(lld v = 1, lld tl = 0, lld tr = n-1){
		if(tl==tr) st[v] = build_leaf(y[tl], tl);
		else{
			lld tm = (tl+tr)/2;
			build(2*v, tl, tm);
			build(2*v+1,tm+1,tr);
			st[v] = merge(st[2*v], st[2*v+1]);
		}
	}

	itemY query(lld l, lld r, lld v = 1, lld tl=0, lld tr=n-1){
		if(l>r) return Y_NEUT;
		if(l==tl&&r==tr) return st[v];
		lld tm = (tl+tr)/2;
		return merge(query(l,min(r,tm),2*v, tl, tm),query(max(l, tm+1), r, 2*v+1, tm+1,tr));
	}

	void upd(lld new_val, lld pos, lld v=1,lld tl=0, lld tr=n-1){
		if(tl==tr) st[v] = build_leaf(new_val, tl);
		else{
			lld tm = (tl+tr)/2;
			if(pos<=tm) upd(new_val, pos, 2*v, tl, tm);
			else upd(new_val, pos, 2*v+1,tm+1,tr);
			st[v] = merge(st[2*v],st[2*v+1]);
		}
	}

};

STX segx;
STY segy;

int calc(){
	auto it = big.end();
	for(int i=0;i<31;i++){
		if(it==big.begin()) break;
		--it;
	}
	auto it2 = it; ++it2;
	lld next_pos = it2==big.end()?n:(*it2);
	itemY mxY = segy.query((*it), next_pos-1);
	lf cur = log((lf)x[(*it)])+log((lf)mxY.val);
	lf mx = cur;
	lld mx_pos = mxY.ind;
	lld prevY = mxY.ind;
	++it;
	while(it!=big.end()){
		cur -= log((lf)y[prevY]);
		it2 = it; ++it2;
		next_pos = it2==big.end()?n:(*it2);
		mxY = segy.query((*it), next_pos-1);
		cur += log((lf)x[(*it)])+log((lf)mxY.val);
		if(cur>mx){
			mx = cur;
			mx_pos = mxY.ind;
		}
		prevY = mxY.ind;
		++it;
	}
	lld res = segx.query(0, mx_pos).val;
	res *= y[mx_pos]; res%=MOD;
	return (int)res;
}

int init(int N, int X[], int Y[]) {
	n = (lld) N;
	x.resize(n); y.resize(n);
	big.insert(0);
	for(lld i=0;i<n;i++){
		x[i] = (lld)X[i]; y[i] = (lld)Y[i];
		if(x[i]>1) big.insert(i);
	}
	segx.init(); segx.build();
	segy.init(); segy.build();
	return calc();
}

int updateX(int pos, int val){
	segx.upd(val, pos);
	x[pos] = val;
	if(val>1){
		big.insert(pos);
	}else if(pos!=0){
		auto it = big.find(pos);
		if(it!=big.end()) big.erase(it);
	}
	return calc();
}

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

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