Submission #65763

#	Time	Username	Problem	Language	Result	Execution time	Memory
65763		Hoget157	Horses (IOI15_horses)	C++14	77 / 100	1512 ms	68492 KiB

horses

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;

ll n;

class RMQ{
	ll seg,ini;
	vector<ll> dat;
	function<ll(ll,ll)> f;
	public:
	RMQ() : seg(1){}
	void init(ll def,function<ll(ll,ll)> F){
		ini = def;
		f = F;
		while(seg < n) seg *= 2;
		dat.resize(seg * 2 - 1);
		for(ll i = 0;i < seg * 2 - 1;i++) dat[i] = ini;
	}
	void update(ll i,ll x){
		i += seg - 1;
		dat[i] = x;
		while(i){
			i = (i - 1) / 2;
			dat[i] = f(dat[i * 2 + 1],dat[i * 2 + 2]);
		}
	}
	ll get(ll a){
		return dat[a + seg - 1];
	}
	ll get(ll a,ll b){
		ll ans = ini,pos = seg;
		while(a != b){
			if(a % 2) ans = f(ans,dat[pos - 1 + a++]);
			if(b % 2) ans = f(ans,dat[pos - 1 + --b]);
			pos /= 2;
			a /= 2;
			b /= 2;
		}
		return ans;
	}
	ll find(ll a,ll b,bool isl,ll k = 0,ll l = 0,ll r = -1){
		if(b == -1) b = seg;
		if(r == -1) r = seg;
		if(dat[k] == 1 || b <= l || r <= a) return -1;
		if(r - l == 1) return l;
		if(isl){
			ll ans = find(a,b,isl,k * 2 + 1,l,(l + r) / 2);
			if(ans != -1) return ans;
			return find(a,b,isl,k * 2 + 2,(l + r) / 2,r);
		}else{
			ll ans = find(a,b,isl,k * 2 + 2,(l + r) / 2,r);
			if(ans != -1) return ans;
			return find(a,b,isl,k * 2 + 1,l,(l + r) / 2);
		}
	}
};

RMQ rmq1,rmq2,seki;

ll calc(){
	ll pos = n - 1,tmp = 1,ma = 0,ans;
	while(pos > 0){
		pos = rmq1.find(0,pos,false);
		ll t = rmq1.get(pos);
		if(tmp * t > 1000000000ll) break;
		tmp *= t;
	}
	ans = seki.get(0,pos + 1);
	tmp = 1;
	while(pos < n - 1){
		ll nxt = rmq1.find(pos + 1,-1,true);
		ma = max(ma,tmp * rmq2.get(pos,nxt));
		tmp *= rmq1.get(nxt);
		pos = nxt;
	}
	return ma % MOD * ans % MOD;
}

ll init(int N,int x[],int y[]){
	n = N + 2;
	rmq1.init(0,[](ll a,ll b){ return max(a,b); });
	rmq2.init(0,[](ll a,ll b){ return max(a,b); });
	seki.init(1,[](ll a,ll b){ return a * b % MOD; });
	rmq1.update(0,MOD);
	rmq1.update(n - 1,MOD);
	for(ll i = 0;i < n - 2;i++){
		rmq1.update(i + 1,x[i]);
		rmq2.update(i + 1,y[i]);
		seki.update(i + 1,x[i]);
	}
	return calc();
}

ll updateX(int pos,int val){
	rmq1.update(pos + 1,val);
	seki.update(pos + 1,val);
	return calc();
}

ll updateY(int pos,int val){
	rmq2.update(pos + 1,val);
	return calc();
}

/*signed main(){
	int N,m,x[500010],y[500010];
	cin >> N;
	for(int i = 0;i < N;i++) cin >> x[i];
	for(int i = 0;i < N;i++) cin >> y[i];
	cin >> m;
	cout << init(N,x,y) << endl;
	for(int i = 0;i < m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		if(a == 1) cout << updateX(b,c) << endl;
		else cout << updateY(b,c) << endl;
	}
	return 0;
}*/

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