Submission #18656

#	Time	Username	Problem	Language	Result	Execution time	Memory
18656		suhgyuho_william	Horses (IOI15_horses)	C++98	34 / 100	88 ms	12812 KiB

horses

#include "horses.h"

int N;
long long ans,sb3;
long long x[500002],y[500002];

#define MOD 1000000007

long long inv(long long value){
	if(value == 1) return 1;
	long long tmp = (inv(MOD%value)*((-value)/MOD));
	tmp %= MOD;
	if(tmp < 0) tmp += MOD;
	return tmp;
}

int process1(){
	int i,t;
	long long tmp;

    ans = x[1];
    t = tmp = 1;
    for(i=2; i<=N; i++){
		tmp *= x[i];
		if(tmp > y[t] || tmp*y[i] > y[t]){
			t = i;
			ans *= (tmp%MOD); ans %= MOD;
			tmp = 1;
		}
    }
    sb3 = 1;
	for(i=1; i<=N-30; i++){
		sb3 *= x[i];
		sb3 %= MOD;
    }
    ans *= y[t];
    ans %= MOD;

	return (int)ans;
}

void subtask3(){
	int i,t;
	long long tmp;

	ans = x[N-29]*sb3; ans %= MOD;
	t = N-29; tmp = 1;
	for(i=N-28; i<=N; i++){
		tmp *= x[i];
		if(tmp > y[t] || tmp*y[i] > y[t]){
			t = i;
			ans *= (tmp%MOD); ans %= MOD;
			tmp = 1;
		}
	}
	ans *= y[t];
	ans %= MOD;
}

int init(int n, int X[], int Y[]) {
    int i;

    for(i=1; i<=n; i++){
		x[i] = (long long)X[i-1];
		y[i] = (long long)Y[i-1];
    }
    N = n;
    process1();
}

int updateX(int pos, int val) {
	pos++;
	if(N <= 1000){ x[pos] = (long long)val; return process1(); }
	if(N-29 <= pos){
		x[pos] = (long long)val;
		subtask3();
	}else{
		ans *= inv(x[pos]); sb3 *= inv(x[pos]);
		ans %= MOD; sb3 %= MOD;
		x[pos] = (long long)val;
		ans *= x[pos]; sb3 *= x[pos];
		ans %= MOD; sb3 %= MOD;
	}
	return (int)ans;
}

int updateY(int pos, int val) {
	pos++;
	if(N <= 1000){ y[pos] = (long long)val; return process1(); }
	if(N-29 <= pos){
		y[pos] = (long long)val;
		subtask3();
	}else{
		y[pos] = (long long)val;
	}
	return (int)ans;
}

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