Submission #1178464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178464		sleepntsheep	Horses (IOI15_horses)	C11	100 / 100	89 ms	33196 KiB

horses

#include "horses.h"
#include <stdio.h>
#include <math.h>

const int M=1000000007;

int n, y[555555], x[555555];

typedef struct A{ double sm,mx; int ans,mul; } A;
A t[1111111];

void pul(int i){
	t[i].mul=t[i*2].mul*1ll*t[i*2+1].mul%M;
	t[i].sm=t[i*2].sm+t[i*2+1].sm;
	if(t[i*2].mx>=t[i*2].sm+t[i*2+1].mx){
		t[i].mx=t[i*2].mx;
		t[i].ans=t[i*2].ans;
	}else{
		t[i].mx=t[i*2].sm+t[i*2+1].mx;
		t[i].ans=t[i*2].mul*1ll*t[i*2+1].ans%M;
	}
}

void o(int i){
	t[i+n]=(A){ log(x[i]),log(x[i])+log(y[i]), x[i]*1ll*y[i]%M,x[i] };
}
void u(int i){
	for(int p=i+n;p/=2;)pul(p);
}

int init(int N, int X[], int Y[]) {
	n=N;
	while((n&(n-1)))++n;
	for(int i=0;i<N;++i) x[i]=X[i],y[i]=Y[i], o(i);
	for(int i=n;--i;)pul(i);
	return t[1].ans;
}

int updateX(int i, int val) {
	x[i]=val;
	o(i);u(i);
	return t[1].ans;
}

int updateY(int pos, int val) {
	y[pos]=val;
	o(pos);u(pos);
	return t[1].ans;
}

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