oj.uz

Submission #1021529

# Submission time Handle Problem Language Result Execution time Memory
1021529 2024-07-12T19:11:40 Z aykhn Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 141676 KB 
#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F3F3F3F3F
#define int long long

const int MXN = 1e6 + 5;

int n, q;
int a[MXN];
vector<int> st[MXN << 2];
int mx[MXN << 2];

void build(int l, int r, int x)
{
	mx[x] = 0;
	if (l == r)
	{
		st[x].push_back(a[l]);
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, 2*x), build(mid + 1, r, 2*x + 1);
	int i = 0, j = 0;
	while (i < st[2*x].size() && j < st[2*x + 1].size())
	{
		if (st[2*x][i] < st[2*x + 1][j]) 
		{
			st[x].push_back(st[2*x][i]);
			i++;
		}
		else 
		{
			st[x].push_back(st[2*x + 1][j]);
			j++;
		}
	}
	while (i < st[2*x].size()) 
	{
		st[x].push_back(st[2*x][i]);
		i++;
	}
	while (j < st[2*x + 1].size()) 
	{
		st[x].push_back(st[2*x + 1][j]);
		j++;
	}
	if (st[2*x].back() > st[2*x + 1][0]) mx[x] = st[2*x].back() + *--lower_bound(st[2*x + 1].begin(), st[2*x + 1].end(), st[2*x].back());
	mx[x] = max({mx[x], mx[2*x], mx[2*x + 1]});
}

vector<int> res;
int get(int l, int r, int x, int lx, int rx)
{
	if (l > rx || r < lx) return -inf;
	if (l >= lx && r <= rx) 
	{
		res.push_back(x);
		return mx[x];
	}
	int mid = (l + r) >> 1;
	return max(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	// build(1, n, 1);
	while (q--)
	{
		// res.clear();
		int l, r, x;
		cin >> l >> r >> x;
		int ans = -inf;
		set<int> s;
		for (int i = r; i >= l; i--)
		{
			auto it = s.lower_bound(a[i]);
			if (it != s.begin()) ans = max(ans, a[i] + *--it);
			s.insert(a[i]);
		}
		cout << (ans <= x) << '\n';
		// int ans = get(1, n, 1, l, r), curmx = -inf;
		// for (int i = 0; i + 1 < res.size(); i++)
		// {
		// 	int l = res[i], r = res[i + 1];
		// 	curmx = max(curmx, st[l].back());
		// 	if (curmx > st[r][0]) ans = max(ans, curmx + *--lower_bound(st[r].begin(), st[r].end(), curmx));
		// }
		// cout << (ans <= x) << '\n';
	}
}

Compilation message

sortbooks.cpp: In function 'void build(long long int, long long int, long long int)':
sortbooks.cpp:26:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  while (i < st[2*x].size() && j < st[2*x + 1].size())
      |         ~~^~~~~~~~~~~~~~~~
sortbooks.cpp:26:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  while (i < st[2*x].size() && j < st[2*x + 1].size())
      |                               ~~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:39:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  while (i < st[2*x].size())
      |         ~~^~~~~~~~~~~~~~~~
sortbooks.cpp:44:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  while (j < st[2*x + 1].size())
      |         ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94688 KB Output is correct
2 Correct 38 ms 94736 KB Output is correct
3 Correct 43 ms 94544 KB Output is correct
4 Correct 40 ms 94664 KB Output is correct
5 Correct 41 ms 94548 KB Output is correct
6 Correct 51 ms 94732 KB Output is correct
7 Correct 62 ms 94556 KB Output is correct
8 Correct 50 ms 94768 KB Output is correct
9 Correct 44 ms 94784 KB Output is correct
10 Correct 41 ms 94748 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94688 KB Output is correct
2 Correct 38 ms 94736 KB Output is correct
3 Correct 43 ms 94544 KB Output is correct
4 Correct 40 ms 94664 KB Output is correct
5 Correct 41 ms 94548 KB Output is correct
6 Correct 51 ms 94732 KB Output is correct
7 Correct 62 ms 94556 KB Output is correct
8 Correct 50 ms 94768 KB Output is correct
9 Correct 44 ms 94784 KB Output is correct
10 Correct 41 ms 94748 KB Output is correct
11 Correct 195 ms 94532 KB Output is correct
12 Correct 624 ms 94544 KB Output is correct
13 Correct 666 ms 94548 KB Output is correct
14 Correct 1101 ms 94964 KB Output is correct
15 Correct 1164 ms 95156 KB Output is correct
16 Correct 1678 ms 94756 KB Output is correct
17 Correct 1229 ms 94700 KB Output is correct
18 Correct 139 ms 94720 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3057 ms 141676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 96184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94688 KB Output is correct
2 Correct 38 ms 94736 KB Output is correct
3 Correct 43 ms 94544 KB Output is correct
4 Correct 40 ms 94664 KB Output is correct
5 Correct 41 ms 94548 KB Output is correct
6 Correct 51 ms 94732 KB Output is correct
7 Correct 62 ms 94556 KB Output is correct
8 Correct 50 ms 94768 KB Output is correct
9 Correct 44 ms 94784 KB Output is correct
10 Correct 41 ms 94748 KB Output is correct
11 Correct 195 ms 94532 KB Output is correct
12 Correct 624 ms 94544 KB Output is correct
13 Correct 666 ms 94548 KB Output is correct
14 Correct 1101 ms 94964 KB Output is correct
15 Correct 1164 ms 95156 KB Output is correct
16 Correct 1678 ms 94756 KB Output is correct
17 Correct 1229 ms 94700 KB Output is correct
18 Correct 139 ms 94720 KB Output is correct
19 Execution timed out 3035 ms 106900 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94688 KB Output is correct
2 Correct 38 ms 94736 KB Output is correct
3 Correct 43 ms 94544 KB Output is correct
4 Correct 40 ms 94664 KB Output is correct
5 Correct 41 ms 94548 KB Output is correct
6 Correct 51 ms 94732 KB Output is correct
7 Correct 62 ms 94556 KB Output is correct
8 Correct 50 ms 94768 KB Output is correct
9 Correct 44 ms 94784 KB Output is correct
10 Correct 41 ms 94748 KB Output is correct
11 Correct 195 ms 94532 KB Output is correct
12 Correct 624 ms 94544 KB Output is correct
13 Correct 666 ms 94548 KB Output is correct
14 Correct 1101 ms 94964 KB Output is correct
15 Correct 1164 ms 95156 KB Output is correct
16 Correct 1678 ms 94756 KB Output is correct
17 Correct 1229 ms 94700 KB Output is correct
18 Correct 139 ms 94720 KB Output is correct
19 Execution timed out 3057 ms 141676 KB Time limit exceeded
20 Halted 0 ms 0 KB -