Submission #18661

#	Time	Username	Problem	Language	Result	Execution time	Memory
18661		suhgyuho_william	Horses (IOI15_horses)	C++98	17 / 100	409 ms	32344 KiB

horses

#include "horses.h"
#include <algorithm>

using namespace std;

int N,nn;
int next[500002],before[500002];
long long ans,mulx;
long long x[500002],y[500002];
long long seg[2000000];

#define MOD 1000000007

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

void update(int node,long long value){
	seg[node] = value;
	node /= 2;
	while(node > 0){
        seg[node] = max(seg[node*2],seg[(node*2)+1]);
		node /= 2;
	}
}

int s,e;
long long big;
void finding(int node,int left,int right){
	if(e < left || right < s) return;
	if(s <= left && right <= e){
		big = max(big,seg[node]);
		return;
	}
	int mid = (left+right)/2;
	finding(node*2,left,mid);
	finding((node*2)+1,mid+1,right);
}
long long get(){
	big = 0;
	finding(1,1,nn);
	return big;
}

long long print[50];
void process(){
	int i,t,cnt;
	long long tmp;

	ans = 0; tmp = 1; cnt = 0;
	t = next[N+1];
	while(t != 0){
        s = t; e = before[t]-1;
        print[++cnt] = get();
        tmp *= x[t];
        if(tmp >= 1000000000) break;
        t = next[t];
	}
	if(t == 0){
		s = 1; e = before[0]-1;
		if(s <= e){
			ans = get();
		}
		tmp = 1; t = before[0];
		for(i=cnt; i>=1; i--){
			tmp *= x[t];
			ans = max(ans,tmp*print[i]);
			t = before[t];
		}
	}else{
        for(i=cnt; i>=1; i--){

        }
	}
}

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

	mulx = 1;
    for(i=1; i<=n; i++){
		x[i] = (long long)X[i-1];
		mulx *= x[i]; mulx %= MOD;
		y[i] = (long long)Y[i-1];
    }
    N = n;
    for(nn=1; nn<N; nn*=2);
	for(i=1; i<=N; i++) update(nn+i-1,y[i]);
	t = N+1;
	for(i=N; i>=1; i--){
		if(x[i] > 1){
			before[i] = t;
			next[t] = i;
			t = i;
		}
	}
	before[0] = t;
	process();
	return (int)ans;
}

int updateX(int pos, int val) {
	pos++;
	mulx *= inv(x[pos]); mulx %= MOD;
	mulx *= (long long)val; mulx %= MOD;
    if(x[pos] == 1 && val > 1){

    }else if(x[pos] > 1 && val == 1){

    }
    x[pos] = (long long)val;
	process();
	return (int)ans;
}

int updateY(int pos, int val) {
	update(nn+pos,val);
	process();
	return (int)ans;
}

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