oj.uz

Submission #18661

# Submission time Handle Problem Language Result Execution time Memory
18661 2016-02-13T13:04:10 Z suhgyuho_william Horses (IOI15_horses) C++
17 / 100
 409 ms 32344 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];
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.0 / 17.0

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

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 28432 KB Output is correct
2 Correct 0 ms 28432 KB Output is correct
3 Correct 0 ms 28432 KB Output is correct
4 Correct 0 ms 28432 KB Output is correct
5 Correct 0 ms 28432 KB Output is correct
6 Correct 0 ms 28432 KB Output is correct
7 Correct 0 ms 28432 KB Output is correct
8 Correct 0 ms 28432 KB Output is correct
9 Correct 0 ms 28432 KB Output is correct
10 Correct 0 ms 28432 KB Output is correct
11 Correct 0 ms 28432 KB Output is correct
12 Correct 0 ms 28432 KB Output is correct
13 Correct 0 ms 28432 KB Output is correct
14 Correct 0 ms 28432 KB Output is correct
15 Correct 0 ms 28432 KB Output is correct
16 Correct 0 ms 28432 KB Output is correct
17 Correct 0 ms 28432 KB Output is correct
18 Correct 0 ms 28432 KB Output is correct
19 Correct 0 ms 28432 KB Output is correct
20 Correct 0 ms 28432 KB Output is correct
21 Incorrect 0 ms 28432 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 409 ms 32344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 28432 KB Output is correct
2 Correct 0 ms 28432 KB Output is correct
3 Correct 0 ms 28432 KB Output is correct
4 Correct 0 ms 28432 KB Output is correct
5 Correct 0 ms 28432 KB Output is correct
6 Correct 0 ms 28432 KB Output is correct
7 Correct 0 ms 28432 KB Output is correct
8 Correct 0 ms 28432 KB Output is correct
9 Correct 0 ms 28432 KB Output is correct
10 Correct 0 ms 28432 KB Output is correct
11 Correct 0 ms 28432 KB Output is correct
12 Correct 0 ms 28432 KB Output is correct
13 Correct 0 ms 28432 KB Output is correct
14 Correct 0 ms 28432 KB Output is correct
15 Correct 0 ms 28432 KB Output is correct
16 Correct 0 ms 28432 KB Output is correct
17 Correct 0 ms 28432 KB Output is correct
18 Correct 0 ms 28432 KB Output is correct
19 Correct 0 ms 28432 KB Output is correct
20 Correct 0 ms 28432 KB Output is correct
21 Incorrect 0 ms 28432 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 28432 KB Output is correct
2 Correct 0 ms 28432 KB Output is correct
3 Correct 0 ms 28432 KB Output is correct
4 Correct 0 ms 28432 KB Output is correct
5 Correct 0 ms 28432 KB Output is correct
6 Correct 0 ms 28432 KB Output is correct
7 Correct 0 ms 28432 KB Output is correct
8 Correct 0 ms 28432 KB Output is correct
9 Correct 0 ms 28432 KB Output is correct
10 Correct 0 ms 28432 KB Output is correct
11 Correct 0 ms 28432 KB Output is correct
12 Correct 0 ms 28432 KB Output is correct
13 Correct 0 ms 28432 KB Output is correct
14 Correct 0 ms 28432 KB Output is correct
15 Correct 0 ms 28432 KB Output is correct
16 Correct 0 ms 28432 KB Output is correct
17 Correct 0 ms 28432 KB Output is correct
18 Correct 0 ms 28432 KB Output is correct
19 Correct 0 ms 28432 KB Output is correct
20 Correct 0 ms 28432 KB Output is correct
21 Incorrect 0 ms 28432 KB Output isn't correct
22 Halted 0 ms 0 KB -