Submission #262424

#	Time	Username	Problem	Language	Result	Execution time	Memory
262424		amiratou	Horses (IOI15_horses)	C++14	100 / 100	464 ms	95864 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
const int MOD = 1000000007;
typedef pair<long double,ll> ii;
ll x[500005],y[500005];
int n;
ii st[2000005],A[500005],lazy[2000005];
void mod(ll& a){
	if(a>=MOD)a%=MOD;
}
int binpow(ll a,ll b){
	if(!b)return 1;
	ll res=binpow(a,b/2);
	res*=res;
	mod(res);
	if(b&1)res*=a,mod(res);
	return (int)res;
}
void build(int node,int l,int r){
	lazy[node]={0,1};
	if(l==r){
		st[node]={A[l].fi+log(y[l]),A[l].se*y[l]};
		mod(st[node].se);
		return;
	}
	int med=(l+r)>>1;
	build(node*2,l,med),build(node*2+1,med+1,r);
	st[node]=max(st[node*2],st[node*2+1]);
}
void prop(int node,int l,int r){
	if(lazy[node].fi){
		st[node].fi+=lazy[node].fi;
		st[node].se*=lazy[node].se;
		mod(st[node].se);
		if(l!=r){
			lazy[node*2].fi+=lazy[node].fi;
			lazy[node*2+1].fi+=lazy[node].fi;
			lazy[node*2].se*=lazy[node].se;
			lazy[node*2+1].se*=lazy[node].se;
			mod(lazy[node*2].se),mod(lazy[node*2+1].se);
		}
		lazy[node]={0,1};
	}
}
void updx(int node,int l,int r,int i,int j,ii val){
	prop(node,l,r);
	if(l>j || r<i)
		return;
	if(l>=i && r<=j){
		lazy[node]=val;
		prop(node,l,r);
		return;
	}
	int med=(l+r)>>1;
	updx(node*2,l,med,i,j,val),updx(node*2+1,med+1,r,i,j,val);
	st[node]=max(st[node*2],st[node*2+1]);
}
void updy(int node,int l,int r,int idx,ii val){
	prop(node,l,r);
	if(l>idx || r<idx)
		return;
	if(l==r){
		st[node].fi+=val.fi;
		st[node].se*=val.se;
		mod(st[node].se);
		return;
	}
	int med=(l+r)>>1;
	updy(node*2,l,med,idx,val),updy(node*2+1,med+1,r,idx,val);
	st[node]=max(st[node*2],st[node*2+1]);
}

int init(int N, int X[], int Y[]) {
	n=N;
	for (int i = 0; i < N; ++i){
		x[i]=X[i],y[i]=Y[i];
		A[i].fi=log(x[i]);
		if(i)A[i].fi+=A[i-1].fi;
		A[i].se=x[i];
		if(i)A[i].se*=A[i-1].se,mod(A[i].se);
	}
	build(1,0,n-1);
	return (int)(st[1].se);
}

int updateX(int pos, int val) {	
	ii h={-log(x[pos]),binpow(x[pos],MOD-2)};
	x[pos]=val;
	h.fi+=log(val),h.se*=val;
	mod(h.se);
	updx(1,0,n-1,pos,n-1,h);
	prop(1,0,n-1);
	return (int)st[1].se;
}

int updateY(int pos, int val) {
	ii h={-log(y[pos]),binpow(y[pos],MOD-2)};
	y[pos]=val;
	h.fi+=log(val),h.se*=val;
	mod(h.se);
	updy(1,0,n-1,pos,h);
	prop(1,0,n-1);
	return (int)st[1].se;
}

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