oj.uz

Submission #1007996

# Submission time Handle Problem Language Result Execution time Memory
1007996 2024-06-26T05:17:25 Z The_Samurai Horses (IOI15_horses) C++17
100 / 100
 232 ms 53348 KB 
#include "horses.h"
#include "bits/stdc++.h"
using namespace std;
const int mod = 1e9 + 7;
using ll = long long;

struct SegTreeY {
	vector<int> tree;
	int size;
	int neutral_element = -1e9;

	int merge(int a, int b) {
		return max(a, b);
	}
	
	void build(const vector<int> &a) {
		size = 1;
		while (size < a.size()) size *= 2;
		tree.assign(2 * size, neutral_element);
		for (int i = size; i < size + a.size(); i++) tree[i] = a[i - size];
		for (int i = size - 1; i > 0; i--) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
	}

	void upd(int i, int v) {
		i += size;
		tree[i] = v;
		for (; i > 1; i >>= 1) tree[i >> 1] = merge(tree[i], tree[i ^ 1]);
	}

	int get(int l, int r) {
		if (l > r) return neutral_element;
		int res = neutral_element;
		for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
			if (l & 1) res = merge(res, tree[l++]);
			if (r & 1) res = merge(res, tree[--r]);
		}
		return res;
	}
};

struct SegTreeX {
	vector<int> tree;
	int size;
	int neutral_element = 1;

	int merge(int a, int b) {
		return 1ll * a * b % mod;
	}
	
	void build(const vector<int> &a) {
		size = 1;
		while (size < a.size()) size *= 2;
		tree.assign(2 * size, neutral_element);
		for (int i = size; i < size + a.size(); i++) tree[i] = a[i - size];
		for (int i = size - 1; i > 0; i--) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
	}

	void upd(int i, int v) {
		i += size;
		tree[i] = v;
		for (; i > 1; i >>= 1) tree[i >> 1] = merge(tree[i], tree[i ^ 1]);
	}

	int get(int l, int r) {
		if (l > r) return neutral_element;
		int res = neutral_element;
		for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
			if (l & 1) res = merge(res, tree[l++]);
			if (r & 1) res = merge(res, tree[--r]);
		}
		return res;
	}
};

int n;
vector<int> x, y;
SegTreeX sgX;
SegTreeY sgY;
set<int, greater<>> st;

int get_ans() {
	vector<tuple<int, int, int>> vec;
	int last = n;
	__int128_t mul = 1;
	for (int i: st) {
		mul *= x[i];
		vec.emplace_back(i, x[i], sgY.get(i, last - 1));
		last = i;
		if (mul > ll(1e9)) break;
	}
	if (vec.empty()) {
		return sgY.get(0, n - 1);
	}
	reverse(vec.begin(), vec.end());
	__int128_t best = 1;
	mul = 1;
	for (auto [i, v1, v2]: vec) {
		// cout << i << ' ' << v1 << ' ' << v2 << endl;
		mul *= v1;
		best = max(best, mul * v2);
	}
	if (best <= ll(1e9) and best * sgX.get(0, get<0>(vec[0]) - 1) < sgY.get(0, n - 1)) {
		best = sgY.get(0, n - 1);
	} else {
		best = best % mod * sgX.get(0, get<0>(vec[0]) - 1) % mod;     
	}
	return best;
}

int init(int N, int X[], int Y[]) {
	n = N;
	x.resize(n), y.resize(n);
	for (int i = 0; i < n; i++) x[i] = X[i], y[i] = Y[i];
	sgX.build(x);
	sgY.build(y);
	for (int i = 0; i < n; i++) {
		if (x[i] > 1) st.insert(i);
	}
	return get_ans();
}

int updateX(int pos, int val) {
	if (x[pos] > 1) st.erase(pos);
	x[pos] = val;
	sgX.upd(pos, val);
	if (x[pos] > 1) st.insert(pos);
	return get_ans();
}

int updateY(int pos, int val) {
	y[pos] = val;
	sgY.upd(pos, val);
	return get_ans();
}

Compilation message

horses.cpp: In member function 'void SegTreeY::build(const std::vector<int>&)':
horses.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   while (size < a.size()) size *= 2;
      |          ~~~~~^~~~~~~~~~
horses.cpp:20:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for (int i = size; i < size + a.size(); i++) tree[i] = a[i - size];
      |                      ~~^~~~~~~~~~~~~~~~~
horses.cpp: In member function 'int SegTreeX::merge(int, int)':
horses.cpp:47:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   47 |   return 1ll * a * b % mod;
      |          ~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void SegTreeX::build(const std::vector<int>&)':
horses.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   while (size < a.size()) size *= 2;
      |          ~~~~~^~~~~~~~~~
horses.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i = size; i < size + a.size(); i++) tree[i] = a[i - size];
      |                      ~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int get_ans()':
horses.cpp:107:9: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  107 |  return best;
      |         ^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 420 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 440 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 42764 KB Output is correct
2 Correct 200 ms 47468 KB Output is correct
3 Correct 184 ms 43100 KB Output is correct
4 Correct 232 ms 48464 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 504 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 24 ms 20552 KB Output is correct
34 Correct 24 ms 20416 KB Output is correct
35 Correct 133 ms 50768 KB Output is correct
36 Correct 129 ms 50772 KB Output is correct
37 Correct 21 ms 18772 KB Output is correct
38 Correct 61 ms 31312 KB Output is correct
39 Correct 18 ms 18520 KB Output is correct
40 Correct 107 ms 45980 KB Output is correct
41 Correct 18 ms 18516 KB Output is correct
42 Correct 19 ms 18576 KB Output is correct
43 Correct 117 ms 46344 KB Output is correct
44 Correct 104 ms 46316 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 436 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 140 ms 44552 KB Output is correct
34 Correct 197 ms 53348 KB Output is correct
35 Correct 164 ms 44912 KB Output is correct
36 Correct 200 ms 48676 KB Output is correct
37 Correct 29 ms 20572 KB Output is correct
38 Correct 25 ms 20564 KB Output is correct
39 Correct 135 ms 50692 KB Output is correct
40 Correct 126 ms 50856 KB Output is correct
41 Correct 27 ms 18776 KB Output is correct
42 Correct 65 ms 31316 KB Output is correct
43 Correct 16 ms 18520 KB Output is correct
44 Correct 128 ms 45860 KB Output is correct
45 Correct 18 ms 18524 KB Output is correct
46 Correct 19 ms 18516 KB Output is correct
47 Correct 106 ms 46320 KB Output is correct
48 Correct 113 ms 46160 KB Output is correct
49 Correct 70 ms 23632 KB Output is correct
50 Correct 55 ms 23628 KB Output is correct
51 Correct 162 ms 52564 KB Output is correct
52 Correct 161 ms 52356 KB Output is correct
53 Correct 86 ms 21840 KB Output is correct
54 Correct 97 ms 35352 KB Output is correct
55 Correct 51 ms 19608 KB Output is correct
56 Correct 178 ms 47700 KB Output is correct
57 Correct 60 ms 20052 KB Output is correct
58 Correct 89 ms 20560 KB Output is correct
59 Correct 114 ms 46344 KB Output is correct