답안 #739119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
739119	2023-05-10T02:35:37 Z	fractlpaca	말 (IOI15_horses)	C++17	17 / 100	90 ms	19364 KB

horses

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

#define v vector
#define ll long long

#define MOD ((ll) 1000000007)

using namespace std;

v<ll> xs;
v<ll> ys;
v<ll> xs_mults;
int n;


// Subtask 1

// int solve() {
// 	int ma = 0;
// 	int pop = 1;
// 	for(int i=0; i<n; i++) {
// 		pop*=xs[i];
// 		ma = max(ma, pop*ys[i]);
// 	}
// 	return ma%MOD;
// }

// int init(int N, int X[], int Y[]) {
// 	n = N;
// 	for (int i=0; i<n; i++) {
// 		xs.push_back(X[i]);
// 		ys.push_back(Y[i]);
// 	}
// 	return solve();
// }

// int updateX(int pos, int val) {
// 	xs[pos] = val;
// 	return solve();
// }

// int updateY(int pos, int val) {
// 	ys[pos] = val;
// 	return solve();
// }


//Subtask 2

// int solve() {
// 	int max_i = n-1;
// 	ll pop = xs[n-1];
// 	for(int i=n-2; i>=0 && i>=n-30; i--) {
// 		if (ys[i] > ys[max_i]*pop) {
// 			max_i = i;
// 			pop=1;
// 		}
// 		pop = min(pop*xs[i], (ll)MOD);
// 	}
// 	return (int) ((xs_mults[max_i+1]*ys[max_i])%MOD);
// }

// int init(int N, int X[], int Y[]) {
// 	n = N;
// 	xs_mults.push_back(1);
// 	for (int i=0; i<n; i++) {
// 		xs.push_back(X[i]);
// 		xs_mults.push_back((xs_mults[i]*X[i])%MOD);
// 		ys.push_back(Y[i]);
// 	}
// }

// int updateX(int pos, int val) {
// 	xs[pos] = val;
// 	return solve();
// }

// int updateY(int pos, int val) {
// 	ys[pos] = val;
// 	return solve();
// }


// Subtask 3

int solve() {
	int max_i = n-1;
	ll pop = xs[n-1];
	for(int i=n-2; i>=0 && i>=n-30; i--) {
		if (ys[i] > ys[max_i]*pop) {
			max_i = i;
			pop=1;
		}
		pop = min(pop*xs[i], (ll)MOD);
	}
	return (int) ((xs_mults[max_i+1]*ys[max_i])%MOD);
}

int init(int N, int X[], int Y[]) {
	n = N;
	xs_mults.push_back(1);
	for (int i=0; i<n; i++) {
		xs.push_back(X[i]);
		xs_mults.push_back((xs_mults[i]*X[i])%MOD);
		ys.push_back(Y[i]);
	}
	return solve();
}

int updateX(int pos, int val) {
	xs[pos] = val;
	return solve();
}

int updateY(int pos, int val) {
	ys[pos] = val;
	return solve();
}

// Subtask 5

// ll query_xs(int L, int R, int l, int r, int index) {
// 	if (r<L || l>R) return 1;
// 	if (l>=L and r<=R) return xs[index];
// 	int mid = (l+r)/2;
// 	ll subl = query_xs(L, R, l, mid, index*2);
// 	ll subr = query_xs(L, R, mid+1, r, index*2+1);
// 	return min(MOD, subl*subr);
// }

// void update_xs(int pos, int value, int l, int r, int index) {
// 	int mid = (l+r)/2;
// 	if (l==r) xs[index] = value;
// 	if (pos <= mid){
// 		update_xs(pos, value, l, mid, index*2);
// 	} else {
// 		update_xs(pos, value, mid+1, r, index*2+1);
// 	}
// 	xs[index] = min(MOD, xs[index*2]*xs[index*2+1]);
// }

// ll query_ys(int L, int R, int l, int r, int index) {
// 	if (r<L || l>R) return 0;
// 	if (l>=L and r<=R) return ys[index];
// 	int mid = (l+r)/2;
// 	ll subl = query_ys(L, R, l, mid, index*2);
// 	ll subr = query_ys(L, R, mid+1, r, index*2+1);
// 	return max(subl, subr);
// }

// void update_ys(int pos, int value, int l, int r, int index) {
// 	int mid = (l+r)/2;
// 	if (l==r) ys[index] = value;
// 	if (pos <= mid){
// 		update_ys(pos, value, l, mid, index*2);
// 	} else {
// 		update_ys(pos, value, mid+1, r, index*2+1);
// 	}
// 	ys[index] = max(ys[index*2], ys[index*2+1]);
// }

// int solve() {
// 	int max_i = n-1;
// 	ll pop = xs[n-1];
// 	for(int i=n-2; i>=0; i--) {
// 		if (ys[i] > ys[max_i]*pop) {
// 			max_i = i;
// 			pop=1;
// 		}
// 		pop = min(pop*xs[i], (ll)MOD);
// 	}

// 	pop=1;
// 	for(int i=0; i<=max_i; i++){
// 		pop = (pop*xs[i])%MOD;
// 	}
// 	return (int) ((pop*ys[max_i])%MOD);
// }

// int init(int N, int X[], int Y[]) {
// 	n = N;
// 	xs = v<ll> (2*n, 1);
// 	ys = v<ll> (2*n, 0);

// 	for (int i=0; i<n; i++) {
// 		update_xs(i, X[i], 0, n-1, 1);
// 		update_ys(i, Y[i], 0, n-1, 1);
// 	}
// 	return solve();
// }

// int updateX(int pos, int val) {
// 	update_xs(pos, val, 0, n-1, 1);
// 	return solve();
// }

// int updateY(int pos, int val) {
// 	update_ys(pos, val, 0, n-1, 1);
// 	return solve();
// }

Subtask #1
17.0 / 17.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct
6	Correct	212 KB	Output is correct
7	Correct	212 KB	Output is correct
8	Correct	212 KB	Output is correct
9	Correct	212 KB	Output is correct
10	Correct	212 KB	Output is correct
11	Correct	212 KB	Output is correct
12	Correct	272 KB	Output is correct
13	Correct	212 KB	Output is correct
14	Correct	212 KB	Output is correct
15	Correct	212 KB	Output is correct
16	Correct	212 KB	Output is correct
17	Correct	212 KB	Output is correct
18	Correct	212 KB	Output is correct
19	Correct	212 KB	Output is correct
20	Correct	212 KB	Output is correct

Subtask #2
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Incorrect	0 ms	212 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	18660 KB	Output is correct
2	Incorrect	90 ms	19364 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct
6	Correct	212 KB	Output is correct
7	Correct	212 KB	Output is correct
8	Correct	212 KB	Output is correct
9	Correct	212 KB	Output is correct
10	Correct	212 KB	Output is correct
11	Correct	212 KB	Output is correct
12	Correct	212 KB	Output is correct
13	Correct	212 KB	Output is correct
14	Correct	256 KB	Output is correct
15	Correct	212 KB	Output is correct
16	Correct	212 KB	Output is correct
17	Correct	212 KB	Output is correct
18	Correct	212 KB	Output is correct
19	Correct	212 KB	Output is correct
20	Correct	224 KB	Output is correct
21	Incorrect	212 KB	Output isn't correct
22	Halted	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Incorrect	0 ms	212 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

답안 #739119

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 0 / 17.0

Subtask #3 0 / 20.0

Subtask #4 0 / 23.0

Subtask #5 0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
0 / 17.0

Subtask #3
0 / 20.0

Subtask #4
0 / 23.0

Subtask #5
0 / 23.0