Submission #65771

#	Time	Username	Problem	Language	Result	Execution time	Memory
65771		Hoget157	Horses (IOI15_horses)	C++14	100 / 100	509 ms	52836 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 pos = seg,ans = 1000000000;
		if(b == -1) b = seg;
		while(a != b){
			if(a % 2 && dat[pos - 1 + a++] != 1) break;
			if(b % 2 && dat[pos - 1 + --b] != 1) break;
			pos /= 2;
			a /= 2;
			b /= 2;
		}
		if(isl){
			pos += a - 2;
			while(pos < seg - 1){
				if(dat[pos * 2 + 1] != 1) pos = pos * 2 + 1;
				else pos = pos * 2 + 2;
			}
		}else{
			pos += b - 1;
			while(pos < seg - 1){
				if(dat[pos * 2 + 2] != 1) pos = pos * 2 + 2;
				else pos = pos * 2 + 1;
			}
		}
		return pos - seg + 1;
	}
};

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;
}*/

Compilation message (stderr)

horses.cpp: In member function 'long long int RMQ::find(long long int, long long int, bool)':
horses.cpp:44:16: warning: unused variable 'ans' [-Wunused-variable]
   ll pos = seg,ans = 1000000000;
                ^~~

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