oj.uz

Submission #46212

# Submission time Handle Problem Language Result Execution time Memory
46212 2018-04-18T03:47:58 Z RayaBurong25_1 Horses (IOI15_horses) C++17
17 / 100
 229 ms 59000 KB 
#include "horses.h"
#include <math.h>
#include <algorithm>
#define MOD 1000000007LL
typedef struct node node;
struct node
{
	long long X, A;
	double lgX, lgA;
};
node Seg[2000005];
int n;
int x[500005], y[500005];
void makeTree(int s, int e, int cell)
{
	if (s == e)
	{
		Seg[cell].X = x[s];
		Seg[cell].A = (x[s]*y[s])%MOD;
		Seg[cell].lgX = log(x[s]);
		Seg[cell].lgA = Seg[cell].lgX + log(y[s]);
		return;
	}
	int m = (s + e)/2;
	makeTree(s, m, 2*cell + 1);
	makeTree(m + 1, e, 2*cell + 2);
	Seg[cell].X = (Seg[2*cell + 1].X*Seg[2*cell + 2].X)%MOD;
	Seg[cell].lgX = Seg[2*cell + 1].lgX + Seg[2*cell + 2].lgX;
	if (Seg[2*cell + 1].lgA > Seg[2*cell + 1].lgX + Seg[2*cell + 2].lgA)
	{
		Seg[cell].lgA = Seg[2*cell + 1].lgA;
		Seg[cell].A = Seg[2*cell + 1].A;
	}
	else
	{
		Seg[cell].lgA = Seg[2*cell + 1].lgX + Seg[2*cell + 2].lgA;
		Seg[cell].A = (Seg[2*cell + 1].X*Seg[2*cell + 2].A)%MOD;
	}
}
int init(int N, int X[], int Y[])
{
	n = N;
	int i;
	for (i = 0; i < n; i++)
		x[i] = X[i];
	for (i = 0; i < n; i++)
		y[i] = Y[i];
	makeTree(0, n - 1, 0);
	return (int) Seg[0].A;
}
void update(int pos, int s, int e, int cell)
{
	if (s == e)
	{
		Seg[cell].X = x[s];
		Seg[cell].A = (x[s]*y[s])%MOD;
		Seg[cell].lgX = log(x[s]);
		Seg[cell].lgA = Seg[cell].lgX + log(y[s]);
		return;
	}
	int m = (s + e)/2;
	if (pos <= m)
		update(pos, s, m, 2*cell + 1);
	else
		update(pos, m + 1, e, 2*cell + 2);
	Seg[cell].X = (Seg[2*cell + 1].X*Seg[2*cell + 2].X)%MOD;
	Seg[cell].lgX = Seg[2*cell + 1].lgX + Seg[2*cell + 2].lgX;
	if (Seg[2*cell + 1].lgA > Seg[2*cell + 1].lgX + Seg[2*cell + 2].lgA)
	{
		Seg[cell].lgA = Seg[2*cell + 1].lgA;
		Seg[cell].A = Seg[2*cell + 1].A;
	}
	else
	{
		Seg[cell].lgA = Seg[2*cell + 1].lgX + Seg[2*cell + 2].lgA;
		Seg[cell].A = (Seg[2*cell + 1].X*Seg[2*cell + 2].A)%MOD;
	}
}
int updateX(int pos, int val)
{
	x[pos] = val;
	update(pos, 0, n - 1, 0);
	return (int) Seg[0].A;
}

int updateY(int pos, int val)
{
	y[pos] = val;
	update(pos, 0, n - 1, 0);
	return (int) Seg[0].A;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 704 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 728 KB Output is correct
9 Correct 2 ms 732 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 2 ms 776 KB Output is correct
12 Correct 2 ms 780 KB Output is correct
13 Correct 2 ms 780 KB Output is correct
14 Correct 11 ms 780 KB Output is correct
15 Correct 2 ms 792 KB Output is correct
16 Correct 2 ms 792 KB Output is correct
17 Correct 2 ms 800 KB Output is correct
18 Correct 2 ms 804 KB Output is correct
19 Correct 2 ms 808 KB Output is correct
20 Correct 2 ms 808 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 46336 KB Output is correct
2 Incorrect 229 ms 59000 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

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