Submission #18666

#	Time	Username	Problem	Language	Result	Execution time	Memory
18666		suhgyuho_william	Horses (IOI15_horses)	C++98	100 / 100	579 ms	40156 KiB

horses

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

using namespace std;

int N,nn;
int next[500002],before[500002];
long long ans,mulx;
long long x[500002],y[500002];
int two[2000000];
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,tt;

	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];
		}
		ans %= MOD;
	}else{ // warning
		tt = mulx * inv(tmp%MOD); tt %= MOD;
		tt *= x[t]; tt %= MOD;
		tmp = 1;
        for(i=cnt; i>=1; i--){
            ans = max(ans,tmp*print[i]);
            t = before[t];
            tmp *= x[t];
        }
        ans %= MOD;
        ans *= tt; ans %= MOD;
	}
}

int init(int n, int X[], int Y[]) {
    int i,j,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;
			j = nn+i-1;
			while(j > 0){
				two[j]++;
				j /= 2;
			}
		}
	}
	before[0] = t;
	process();
	return (int)ans;
}

int s2,e2,found;
void find2(int node,int left,int right){
	if(found != -1) return;
	if(e2 < left || right < s2) return;
	if(s2 <= left && right <= e2){
		if(two[node] != 0){
			found = node;
		}

		return;
	}
	int mid = (left+right)/2;
	find2(node*2,left,mid);
	find2((node*2)+1,mid+1,right);
}

int updateX(int pos, int val) {
	int t;

	pos++;
	mulx *= inv(x[pos]); mulx %= MOD;
	mulx *= (long long)val; mulx %= MOD;
    if(x[pos] == 1 && val > 1){
    	if(pos == N){
			before[N] = N+1;
			next[N] = next[N+1];
			next[N+1] = N;
			before[next[N]] = N;
    	}else{
			s2 = pos+1; e2 = N; found = -1;
			find2(1,1,nn);
			if(found == -1) found = N+1;
			else{
				while(found < nn){
					if(two[found*2] != 0) found = (found*2);
					else found = (found*2)+1;
				}
				found -= (nn-1);
			}
			next[pos] = next[found];
			before[pos] = found;
			before[next[found]] = pos;
			next[found] = pos;
    	}
    	t = nn+pos-1;
    	while(t > 0){
			two[t]++;
			t /= 2;
    	}
    }else if(x[pos] > 1 && val == 1){
    	next[before[pos]] = next[pos];
    	before[next[pos]] = before[pos];
		t = nn+pos-1;
		while(t > 0){
			two[t]--;
			t /= 2;
		}
    }
    x[pos] = (long long)val;
	process();
	if(ans < 0) exit(0);
	return (int)ans;
}

int updateY(int pos, int val) {
	update(nn+pos,(long long)val);
	process();
	if(ans < 0) exit(0);
	return (int)ans;
}

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