oj.uz

Submission #18662

# Submission time Handle Problem Language Result Execution time Memory
18662 2016-02-13T13:21:40 Z suhgyuho_william Horses (IOI15_horses) C++
17 / 100
 73 ms 40152 KB 
#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];
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];
		}
	}else{
		tt = mulx * inv(tmp); tt %= MOD;
		tmp = 1;
        for(i=cnt; i>=1; i--){
			tmp *= x[t];
            ans = max(ans,tmp*print[i]);
            t = before[t];
        }
        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;
			next[pos] = next[found];
			before[pos] = found;
			next[found] = pos;
			before[next[found]] = pos;
    	}
    	t = nn+pos-1;
    	while(t > 0){
			two[t]++;
			t /= 2;
    	}
    }else if(x[pos] > 1 && val == 1){
		t = nn+pos-1;
		while(t > 0){
			two[t]--;
			t /= 2;
		}
    }
    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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 36244 KB Output is correct
2 Correct 0 ms 36244 KB Output is correct
3 Correct 0 ms 36244 KB Output is correct
4 Correct 0 ms 36244 KB Output is correct
5 Correct 0 ms 36244 KB Output is correct
6 Correct 0 ms 36244 KB Output is correct
7 Correct 0 ms 36244 KB Output is correct
8 Correct 0 ms 36244 KB Output is correct
9 Correct 0 ms 36244 KB Output is correct
10 Correct 0 ms 36244 KB Output is correct
11 Correct 0 ms 36244 KB Output is correct
12 Correct 0 ms 36244 KB Output is correct
13 Correct 1 ms 36244 KB Output is correct
14 Correct 0 ms 36244 KB Output is correct
15 Correct 0 ms 36244 KB Output is correct
16 Correct 0 ms 36244 KB Output is correct
17 Correct 0 ms 36244 KB Output is correct
18 Correct 0 ms 36244 KB Output is correct
19 Correct 0 ms 36244 KB Output is correct
20 Correct 0 ms 36244 KB Output is correct

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 36244 KB Output is correct
2 Correct 0 ms 36244 KB Output is correct
3 Correct 0 ms 36244 KB Output is correct
4 Correct 0 ms 36244 KB Output is correct
5 Correct 0 ms 36244 KB Output is correct
6 Correct 0 ms 36244 KB Output is correct
7 Correct 0 ms 36244 KB Output is correct
8 Correct 0 ms 36244 KB Output is correct
9 Correct 0 ms 36244 KB Output is correct
10 Correct 0 ms 36244 KB Output is correct
11 Correct 0 ms 36244 KB Output is correct
12 Correct 0 ms 36244 KB Output is correct
13 Correct 0 ms 36244 KB Output is correct
14 Correct 0 ms 36244 KB Output is correct
15 Correct 0 ms 36244 KB Output is correct
16 Correct 0 ms 36244 KB Output is correct
17 Correct 0 ms 36244 KB Output is correct
18 Correct 0 ms 36244 KB Output is correct
19 Correct 0 ms 36244 KB Output is correct
20 Correct 0 ms 36244 KB Output is correct
21 Runtime error 0 ms 36244 KB SIGFPE Floating point exception
22 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 40152 KB SIGFPE Floating point exception
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 36244 KB Output is correct
2 Correct 0 ms 36244 KB Output is correct
3 Correct 0 ms 36244 KB Output is correct
4 Correct 0 ms 36244 KB Output is correct
5 Correct 0 ms 36244 KB Output is correct
6 Correct 0 ms 36244 KB Output is correct
7 Correct 0 ms 36244 KB Output is correct
8 Correct 0 ms 36244 KB Output is correct
9 Correct 0 ms 36244 KB Output is correct
10 Correct 0 ms 36244 KB Output is correct
11 Correct 0 ms 36244 KB Output is correct
12 Correct 0 ms 36244 KB Output is correct
13 Correct 0 ms 36244 KB Output is correct
14 Correct 0 ms 36244 KB Output is correct
15 Correct 0 ms 36244 KB Output is correct
16 Correct 0 ms 36244 KB Output is correct
17 Correct 0 ms 36244 KB Output is correct
18 Correct 0 ms 36244 KB Output is correct
19 Correct 0 ms 36244 KB Output is correct
20 Correct 0 ms 36244 KB Output is correct
21 Runtime error 0 ms 36244 KB SIGFPE Floating point exception
22 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 36244 KB Output is correct
2 Correct 0 ms 36244 KB Output is correct
3 Correct 0 ms 36244 KB Output is correct
4 Correct 0 ms 36244 KB Output is correct
5 Correct 0 ms 36244 KB Output is correct
6 Correct 0 ms 36244 KB Output is correct
7 Correct 0 ms 36244 KB Output is correct
8 Correct 0 ms 36244 KB Output is correct
9 Correct 0 ms 36244 KB Output is correct
10 Correct 0 ms 36244 KB Output is correct
11 Correct 0 ms 36244 KB Output is correct
12 Correct 0 ms 36244 KB Output is correct
13 Correct 0 ms 36244 KB Output is correct
14 Correct 0 ms 36244 KB Output is correct
15 Correct 0 ms 36244 KB Output is correct
16 Correct 0 ms 36244 KB Output is correct
17 Correct 0 ms 36244 KB Output is correct
18 Correct 0 ms 36244 KB Output is correct
19 Correct 0 ms 36244 KB Output is correct
20 Correct 0 ms 36244 KB Output is correct
21 Runtime error 0 ms 36244 KB SIGFPE Floating point exception
22 Halted 0 ms 0 KB -