oj.uz

Submission #838542

# Submission time Handle Problem Language Result Execution time Memory
838542 2023-08-27T11:19:39 Z adrilen Horses (IOI15_horses) C++17
17 / 100
 122 ms 25448 KB 
#include "horses.h"
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int maxn = 5e5, bit = 19;
constexpr ll mod = 1e9 + 7, siz = (1ll << bit);
using pii = pair<ll, bool>;

struct node {
	ll gfac; // Growth factor
	int best_pos;
	bool over_mod;
};

int n;
node segtree[siz * 2] = { 0 };
ll prices[siz] = { 0 };

void fm(ll &a)
{
	if (a >= mod) 
	{
		a %= mod;
	}
}


pair<ll, bool> query(int p, int l, int r, int gl, int gr)
{
	if (gl > gr) assert(0);

	if (l > gr || gl > r) return {1, false};
	// cout << l << " " << r << "\n";

	if (gl <= l && r <= gr) return {segtree[p].gfac, segtree[p].over_mod};

	int mid = (l + r) >> 1;
	pii le = query(p * 2, l, mid, gl, gr), ri = query(p * 2 + 1, mid + 1, r, gl, gr);

	le.first *= ri.first;
	le.second |= (ri.second || (le.first >= mod));
	fm(le.first);
	return le;
}


bool test_pos(int a, int b)
{
	int swapped = 0;
	if (a > b)
	{
		swap(a, b);
		swapped = 1;
	}


	pii le = {prices[a], false};
	pii re = query(1, 0, siz - 1, a + 1, b);

	re.first *= prices[b];
	re.second |= (re.first >= mod);

	// cout << a << " " << b << "\t" << le.first << " " << re.first << "\n";


	if (re.second) return 1 ^ swapped;
	if (re.first > le.first) return 1 ^ swapped;
	return 0 ^ swapped;
}


node comp(node a, const node &b)
{
	a.gfac *= b.gfac;
	a.over_mod |= (b.over_mod || (a.gfac >= mod));
	fm(a.gfac);

	return a;
}

void best_pos_comp(node &o, node &a, node &b)
{
	// cout << a.best_pos << " " << b.best_pos << "\n";
	if (test_pos(a.best_pos, b.best_pos))
	{
		o.best_pos = b.best_pos;
	} else {
		o.best_pos = a.best_pos;
	}
}

ll get_val_pos(int p)
{
	ll out = query(1, 0, siz - 1, 0, p).first * prices[p];
	fm(out);
	return out;
}

int init(int N, int X[], int Y[]) {
	n = N;

	for (int i = 0; i < n; i++)
	{
		prices[i] = Y[i];
		segtree[i + siz] = node{X[i], i, false};
	}

	for (int i = n; i < siz; i++)
	{
		segtree[i + siz] = node{1, i, false};
	}

	// for (int i = 1; i < siz * 2; i++)
	// {
	// 	if (__builtin_popcount(i) == 1) cout << "\n";

	// 	cout << segtree[i].gfac << " " << segtree[i].best_pos << "\t";
	// }
	// cout << "\n";

	for (int i = siz - 1; i > 0; i--)
	{
		segtree[i] = comp(segtree[i * 2], segtree[i * 2 + 1]);
	}

	// for (int i = 1; i < siz * 2; i++)
	// {
	// 	if (__builtin_popcount(i) == 1) cout << "\n";

	// 	cout << segtree[i].gfac << " " << segtree[i].best_pos << "\t";
	// }
	// cout << "\n";

	for (int i = siz - 1; i > 0; i--)
	{
		best_pos_comp(segtree[i], segtree[i * 2], segtree[i * 2 + 1]);

	}


	// for (int i = 1; i < siz * 2; i++)
	// {
	// 	if (__builtin_popcount(i) == 1) cout << "\n";

	// 	cout << segtree[i].gfac << " " << segtree[i].best_pos << "\t";
	// }
	// cout << "\n";
	// cout << segtree[1].best_pos << "\n";
	return (int)get_val_pos(segtree[1].best_pos);
}

int updateX(int pos, int val) {
	pos += val;
	return pos;
}

int updateY(int pos, int val) {
	pos += val;

	return pos;
}

Compilation message

horses.cpp:17:29: warning: missing initializer for member 'node::best_pos' [-Wmissing-field-initializers]
   17 | node segtree[siz * 2] = { 0 };
      |                             ^
horses.cpp:17:29: warning: missing initializer for member 'node::over_mod' [-Wmissing-field-initializers]

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 16704 KB Output is correct
2 Correct 90 ms 16708 KB Output is correct
3 Correct 91 ms 16720 KB Output is correct
4 Correct 112 ms 16724 KB Output is correct
5 Correct 87 ms 16704 KB Output is correct
6 Correct 86 ms 16724 KB Output is correct
7 Correct 91 ms 16724 KB Output is correct
8 Correct 95 ms 16716 KB Output is correct
9 Correct 89 ms 16724 KB Output is correct
10 Correct 89 ms 16832 KB Output is correct
11 Correct 89 ms 16704 KB Output is correct
12 Correct 92 ms 16720 KB Output is correct
13 Correct 89 ms 16692 KB Output is correct
14 Correct 88 ms 16596 KB Output is correct
15 Correct 98 ms 16704 KB Output is correct
16 Correct 88 ms 16724 KB Output is correct
17 Correct 91 ms 16596 KB Output is correct
18 Correct 89 ms 16708 KB Output is correct
19 Correct 85 ms 16704 KB Output is correct
20 Correct 96 ms 16724 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 16704 KB Output is correct
2 Correct 88 ms 16708 KB Output is correct
3 Correct 88 ms 16724 KB Output is correct
4 Correct 91 ms 16708 KB Output is correct
5 Correct 87 ms 16596 KB Output is correct
6 Correct 91 ms 16692 KB Output is correct
7 Correct 122 ms 16700 KB Output is correct
8 Correct 93 ms 16728 KB Output is correct
9 Correct 87 ms 16708 KB Output is correct
10 Correct 116 ms 16716 KB Output is correct
11 Correct 86 ms 16712 KB Output is correct
12 Correct 88 ms 16708 KB Output is correct
13 Correct 86 ms 16664 KB Output is correct
14 Correct 90 ms 16708 KB Output is correct
15 Correct 93 ms 16724 KB Output is correct
16 Correct 93 ms 16716 KB Output is correct
17 Correct 89 ms 16596 KB Output is correct
18 Correct 92 ms 16724 KB Output is correct
19 Correct 89 ms 16716 KB Output is correct
20 Correct 88 ms 16728 KB Output is correct
21 Incorrect 102 ms 16720 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 16720 KB Output is correct
2 Correct 92 ms 16708 KB Output is correct
3 Correct 89 ms 16720 KB Output is correct
4 Correct 94 ms 16708 KB Output is correct
5 Correct 86 ms 16704 KB Output is correct
6 Correct 88 ms 16704 KB Output is correct
7 Correct 95 ms 16724 KB Output is correct
8 Correct 89 ms 16724 KB Output is correct
9 Correct 97 ms 16724 KB Output is correct
10 Correct 93 ms 16708 KB Output is correct
11 Correct 86 ms 16596 KB Output is correct
12 Correct 98 ms 16728 KB Output is correct
13 Correct 88 ms 16712 KB Output is correct
14 Correct 85 ms 16596 KB Output is correct
15 Correct 89 ms 16720 KB Output is correct
16 Correct 87 ms 16708 KB Output is correct
17 Correct 87 ms 16708 KB Output is correct
18 Correct 86 ms 16724 KB Output is correct
19 Correct 86 ms 16724 KB Output is correct
20 Correct 92 ms 16704 KB Output is correct
21 Incorrect 90 ms 16716 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 16596 KB Output is correct
2 Correct 88 ms 16708 KB Output is correct
3 Correct 97 ms 16704 KB Output is correct
4 Correct 95 ms 16724 KB Output is correct
5 Correct 88 ms 16708 KB Output is correct
6 Correct 88 ms 16712 KB Output is correct
7 Correct 90 ms 16720 KB Output is correct
8 Correct 87 ms 16720 KB Output is correct
9 Correct 91 ms 16708 KB Output is correct
10 Correct 96 ms 16708 KB Output is correct
11 Correct 87 ms 16712 KB Output is correct
12 Correct 88 ms 16704 KB Output is correct
13 Correct 107 ms 16596 KB Output is correct
14 Correct 90 ms 16724 KB Output is correct
15 Correct 89 ms 16596 KB Output is correct
16 Correct 95 ms 16712 KB Output is correct
17 Correct 90 ms 16724 KB Output is correct
18 Correct 90 ms 16724 KB Output is correct
19 Correct 88 ms 16704 KB Output is correct
20 Correct 92 ms 16708 KB Output is correct
21 Incorrect 97 ms 16708 KB Output isn't correct
22 Halted 0 ms 0 KB -