oj.uz

Submission #1040322

# Submission time Handle Problem Language Result Execution time Memory
1040322 2024-08-01T01:06:30 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 581 ms 47440 KB 
#include<bits/stdc++.h>
#define INF 1e18
#define fi first
#define se second
#define FOR(i, k, n) for(ll i = k; i <= n; i++)
#define FOR1(i, k, n) for(ll i = k; i >= n; i--)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define re return 0
#define mii map<int, int>
#define input "BAI1.inp"
#define output "BAI1.out"
#define rf 	freopen(input, "r", stdin); freopen(output, "w", stdout)
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int a[maxn];
int T[maxn * 4];
void update(int id, int l, int r, int pos, int val)
{
	if(l == r)
	{
		T[id] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid)
		update(id * 2, l, mid, pos, val);
	else
		update(id * 2 + 1, mid + 1, r, pos, val);
	T[id] = max(T[id * 2], T[id * 2 + 1]);
}
int get(int id, int l, int r, int u, int v)
{
	if(l > v || r < u)
		return 0;
	if(l >= u && r <= v)
		return T[id];
	int mid = (l + r) >> 1;
	return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
int main()
{
	fastio;
	int n, m;
	cin >> n >> m;
	FOR(i, 1, n)
		cin >> a[i];
	if(n <= 5000 && m <= 5000)
	{
		while(m--)
		{
			int l, r, x;
			cin >> l >> r >> x;
			int ans = 0;
			int maxx = a[l];
			FOR(i, l + 1, r)
			{
				if(a[i] < maxx)
					ans = max(ans, maxx + a[i]);
				else
					maxx = a[i];
			}
			cout << (ans <= x) << "\n";
		}
		re;
	}
	stack<int> st;
	st.push(0);
	a[0] = 1e9 + 5;
	FOR(i, 1, n)
	{
		while(a[st.top()] <= a[i])
			st.pop();
		update(1, 1, n, i, st.top());
		st.push(i);
	}
	while(m--)
	{
		int l, r, x;
		cin >> l >> r >> x;
		int res = get(1, 1, n, l, r);
		if(res >= l)
			cout << "0\n";
		else
			cout << "1\n";
	}
	re;
}

Subtask #1
8.0 / 8.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 1 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 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 1 ms 348 KB Output is correct

Subtask #2
9.0 / 9.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 1 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 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 1 ms 348 KB Output is correct
11 Correct 2 ms 556 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 4 ms 472 KB Output is correct
14 Correct 6 ms 476 KB Output is correct
15 Correct 7 ms 608 KB Output is correct
16 Correct 10 ms 612 KB Output is correct
17 Correct 6 ms 596 KB Output is correct
18 Correct 9 ms 348 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 45360 KB Output is correct
2 Correct 581 ms 47368 KB Output is correct
3 Correct 566 ms 47200 KB Output is correct
4 Correct 576 ms 47200 KB Output is correct
5 Correct 548 ms 47440 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.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 1 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 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 1 ms 348 KB Output is correct
11 Correct 2 ms 556 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 4 ms 472 KB Output is correct
14 Correct 6 ms 476 KB Output is correct
15 Correct 7 ms 608 KB Output is correct
16 Correct 10 ms 612 KB Output is correct
17 Correct 6 ms 596 KB Output is correct
18 Correct 9 ms 348 KB Output is correct
19 Incorrect 101 ms 10060 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.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 1 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 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 1 ms 348 KB Output is correct
11 Correct 2 ms 556 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 4 ms 472 KB Output is correct
14 Correct 6 ms 476 KB Output is correct
15 Correct 7 ms 608 KB Output is correct
16 Correct 10 ms 612 KB Output is correct
17 Correct 6 ms 596 KB Output is correct
18 Correct 9 ms 348 KB Output is correct
19 Correct 556 ms 45360 KB Output is correct
20 Correct 581 ms 47368 KB Output is correct
21 Correct 566 ms 47200 KB Output is correct
22 Correct 576 ms 47200 KB Output is correct
23 Correct 548 ms 47440 KB Output is correct
24 Incorrect 54 ms 4012 KB Output isn't correct
25 Halted 0 ms 0 KB -