oj.uz

답안 #138787

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138787 2019-07-30T10:24:16 Z Sorting 말 (IOI15_horses) C++14
54 / 100
 1500 ms 33536 KB 
#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int N = 5e5 + 7;
const long long T = 1e9;

int n, *x, *y;
int first;
bool ok = false;

struct Node{
	long long prefix;

	Node(){
		prefix = 1;
	}
};

inline long long Multiply(long long lvalue, long long rvalue){
	return ((lvalue % mod) * (rvalue % mod) % mod); 
}

long long FastPow(long long base, long long exp){
	if(exp == 0){
		return 1ll;
	}

	if(exp & 1){
		return Multiply(base, FastPow(base, exp - 1));
	}

	long long t = FastPow(base, (exp >> 1ll));

	return Multiply(t, t);
}

Node st[4 * N];

void Update(int idx, int l, int r, int sl, int sr, long long mul){
	if(sl > r || sr < l){
		return;
	}
	if(sl <= l && r <= sr){
		st[idx].prefix = Multiply(st[idx].prefix, mul);

		return;
	}

	st[2 * idx].prefix = Multiply(st[idx].prefix, st[2 * idx].prefix);
	st[2 * idx + 1].prefix = Multiply(st[idx].prefix, st[2 * idx + 1].prefix);
	st[idx].prefix = 1;

	int mid = (l + r) >> 1;

	Update(2 * idx, l, mid, sl, sr, mul);
	Update(2 * idx + 1, mid + 1, r, sl, sr, mul);
}

long long Query(int idx, int l, int r, int s){
	if(s < l || s > r){
		return 1;
	}
	if(l == r){
		return st[idx].prefix;
	}

	st[2 * idx].prefix = Multiply(st[idx].prefix, st[2 * idx].prefix);
	st[2 * idx + 1].prefix = Multiply(st[idx].prefix, st[2 * idx + 1].prefix);
	st[idx].prefix = 1;

	int mid = (l + r) >> 1;

	long long ans = 1;
	ans = Multiply(ans, Query(2 * idx, l, mid, s));
	ans = Multiply(ans, Query(2 * idx + 1, mid + 1, r, s));

	return ans;
}

long long init(int _n, int _x[], int _y[]){
	if(!ok){
		n = _n;
		x = _x;
		y = _y;
		ok = true;

		for(int i = 0; i < n; i++){
			Update(1, 0, n - 1, i, n - 1, x[i]);
		}
	}

	long long curr = 1, ans = 0;

	for(int i = n - 1; i >= 0; i--){
		curr *= (long long) x[i];

		first = i;
		if(curr > T){
			break;
		}
	}

	curr = 1;

	for(int i = first; i < n; i++){
		ans = max(ans, (long long)curr * (long long)y[i]);
		if(i != n - 1){
			curr *= (long long)x[i + 1];
		}
	}
	ans %= mod;

	ans = Multiply(ans, Query(1, 0, n - 1, first));

	return ans;
}

long long updateX(int pos, int val){
	Update(1, 0, n - 1, pos, n - 1, Multiply(val, FastPow(x[pos], mod - 2ll)));
	x[pos] = val;

	return init(n, x, y);
}

long long updateY(int pos, int val){
	y[pos] = val;

	return init(n, x, y);
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 15992 KB Output is correct
2 Correct 15 ms 15992 KB Output is correct
3 Correct 14 ms 15992 KB Output is correct
4 Correct 14 ms 15992 KB Output is correct
5 Correct 14 ms 15992 KB Output is correct
6 Correct 14 ms 15992 KB Output is correct
7 Correct 14 ms 15864 KB Output is correct
8 Correct 14 ms 15992 KB Output is correct
9 Correct 14 ms 15972 KB Output is correct
10 Correct 14 ms 15992 KB Output is correct
11 Correct 14 ms 15992 KB Output is correct
12 Correct 15 ms 15964 KB Output is correct
13 Correct 18 ms 15992 KB Output is correct
14 Correct 15 ms 15976 KB Output is correct
15 Correct 19 ms 15992 KB Output is correct
16 Correct 17 ms 15992 KB Output is correct
17 Correct 19 ms 15992 KB Output is correct
18 Correct 22 ms 15992 KB Output is correct
19 Correct 15 ms 15992 KB Output is correct
20 Correct 15 ms 15996 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 15992 KB Output is correct
2 Correct 14 ms 15992 KB Output is correct
3 Correct 14 ms 15992 KB Output is correct
4 Correct 14 ms 15992 KB Output is correct
5 Correct 14 ms 15992 KB Output is correct
6 Correct 14 ms 15964 KB Output is correct
7 Correct 14 ms 16004 KB Output is correct
8 Correct 15 ms 15976 KB Output is correct
9 Correct 14 ms 15992 KB Output is correct
10 Correct 14 ms 15992 KB Output is correct
11 Correct 14 ms 15992 KB Output is correct
12 Correct 14 ms 16120 KB Output is correct
13 Correct 14 ms 15992 KB Output is correct
14 Correct 14 ms 15992 KB Output is correct
15 Correct 14 ms 15992 KB Output is correct
16 Correct 17 ms 15992 KB Output is correct
17 Correct 17 ms 16168 KB Output is correct
18 Correct 14 ms 15992 KB Output is correct
19 Correct 15 ms 15992 KB Output is correct
20 Correct 14 ms 15992 KB Output is correct
21 Correct 20 ms 15992 KB Output is correct
22 Correct 17 ms 16036 KB Output is correct
23 Correct 16 ms 15992 KB Output is correct
24 Correct 16 ms 16024 KB Output is correct
25 Correct 16 ms 15992 KB Output is correct
26 Correct 19 ms 15992 KB Output is correct
27 Correct 16 ms 15992 KB Output is correct
28 Correct 20 ms 15992 KB Output is correct
29 Correct 19 ms 15992 KB Output is correct
30 Correct 17 ms 15992 KB Output is correct
31 Correct 18 ms 16124 KB Output is correct
32 Correct 18 ms 15992 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 288 ms 20856 KB Output is correct
2 Correct 400 ms 33536 KB Output is correct
3 Correct 356 ms 24692 KB Output is correct
4 Correct 430 ms 28664 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 16120 KB Output is correct
2 Correct 14 ms 15992 KB Output is correct
3 Correct 15 ms 15972 KB Output is correct
4 Correct 14 ms 15992 KB Output is correct
5 Correct 14 ms 15992 KB Output is correct
6 Correct 14 ms 15992 KB Output is correct
7 Correct 14 ms 15992 KB Output is correct
8 Correct 14 ms 15992 KB Output is correct
9 Correct 15 ms 15960 KB Output is correct
10 Correct 15 ms 15992 KB Output is correct
11 Correct 14 ms 15992 KB Output is correct
12 Correct 14 ms 15996 KB Output is correct
13 Correct 14 ms 15992 KB Output is correct
14 Correct 14 ms 15992 KB Output is correct
15 Correct 14 ms 15992 KB Output is correct
16 Correct 14 ms 15992 KB Output is correct
17 Correct 14 ms 15992 KB Output is correct
18 Correct 14 ms 15992 KB Output is correct
19 Correct 14 ms 15992 KB Output is correct
20 Correct 14 ms 15992 KB Output is correct
21 Correct 14 ms 15992 KB Output is correct
22 Correct 15 ms 15964 KB Output is correct
23 Correct 16 ms 16160 KB Output is correct
24 Correct 15 ms 15992 KB Output is correct
25 Correct 16 ms 15992 KB Output is correct
26 Correct 16 ms 15964 KB Output is correct
27 Correct 16 ms 15992 KB Output is correct
28 Correct 17 ms 15992 KB Output is correct
29 Correct 19 ms 15992 KB Output is correct
30 Correct 17 ms 15996 KB Output is correct
31 Correct 19 ms 15992 KB Output is correct
32 Correct 17 ms 16044 KB Output is correct
33 Correct 319 ms 20268 KB Output is correct
34 Correct 233 ms 23956 KB Output is correct
35 Correct 272 ms 30904 KB Output is correct
36 Correct 261 ms 30840 KB Output is correct
37 Correct 856 ms 22308 KB Output is correct
38 Correct 237 ms 23052 KB Output is correct
39 Execution timed out 1525 ms 22008 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 15992 KB Output is correct
2 Correct 15 ms 15992 KB Output is correct
3 Correct 15 ms 16044 KB Output is correct
4 Correct 15 ms 15992 KB Output is correct
5 Correct 18 ms 15992 KB Output is correct
6 Correct 15 ms 15996 KB Output is correct
7 Correct 15 ms 15992 KB Output is correct
8 Correct 19 ms 15992 KB Output is correct
9 Correct 18 ms 15992 KB Output is correct
10 Correct 14 ms 15992 KB Output is correct
11 Correct 15 ms 15992 KB Output is correct
12 Correct 15 ms 15992 KB Output is correct
13 Correct 18 ms 15992 KB Output is correct
14 Correct 15 ms 15992 KB Output is correct
15 Correct 15 ms 15992 KB Output is correct
16 Correct 14 ms 15992 KB Output is correct
17 Correct 15 ms 15992 KB Output is correct
18 Correct 14 ms 15992 KB Output is correct
19 Correct 17 ms 15992 KB Output is correct
20 Correct 15 ms 15992 KB Output is correct
21 Correct 14 ms 15992 KB Output is correct
22 Correct 14 ms 15992 KB Output is correct
23 Correct 16 ms 15980 KB Output is correct
24 Correct 16 ms 15992 KB Output is correct
25 Correct 16 ms 15996 KB Output is correct
26 Correct 16 ms 15992 KB Output is correct
27 Correct 16 ms 15992 KB Output is correct
28 Correct 16 ms 16120 KB Output is correct
29 Correct 17 ms 15992 KB Output is correct
30 Correct 16 ms 15992 KB Output is correct
31 Correct 18 ms 15992 KB Output is correct
32 Correct 18 ms 16036 KB Output is correct
33 Correct 288 ms 22652 KB Output is correct
34 Correct 393 ms 33532 KB Output is correct
35 Correct 359 ms 24664 KB Output is correct
36 Correct 432 ms 28688 KB Output is correct
37 Correct 320 ms 23928 KB Output is correct
38 Correct 232 ms 23928 KB Output is correct
39 Correct 259 ms 30852 KB Output is correct
40 Correct 258 ms 30840 KB Output is correct
41 Correct 862 ms 22392 KB Output is correct
42 Correct 230 ms 22956 KB Output is correct
43 Execution timed out 1550 ms 22032 KB Time limit exceeded
44 Halted 0 ms 0 KB -