oj.uz

Submission #344684

# Submission time Handle Problem Language Result Execution time Memory
344684 2021-01-06T07:42:01 Z _ani Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
47 / 100
 2523 ms 126504 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1'000'002;
const int K = 20;
int w[N], p[1002];
int lg[N];
int mx[N][K];
int diff[N], t[4 * N];
bool f = true;
vector<int> prv[1002];
vector<pair<int, int>> s;
struct el {
	int l, r, k, ind, ans;
}query[N];
bool operator<(const el& a, const el& b) {
	if (a.r == b.r)
		return a.l < b.l;
	return a.r < b.r;
}
bool het(const el& a, const el& b) {
	return a.ind < b.ind;
}
void PoqrSolve(int n, int m) {
	for (int q = 0; q < m; q++) {
		int tmpmx = 0;
		bool ok = true;
		for (int i = query[q].l; i <= query[q].r; i++) {
			if (w[i] < tmpmx && w[i] + tmpmx > query[q].k) {
				query[q].ans = 0;
				ok = false;
				break;
			}
			tmpmx = max(tmpmx, w[i]);
		}
		if (ok)
			query[q].ans = 1;
	}
}
void Buildsegtree(int v, int vl, int vr) {
	if (vl == vr) {
		t[v] = diff[vl];
		return;
	}
	int m = (vl + vr) / 2;
	Buildsegtree(v * 2, vl, m);
	Buildsegtree(v * 2 + 1, m + 1, vr);
	t[v] = min(t[v * 2], t[v * 2 + 1]);
}
int Mn(int v, int vl, int vr, int l, int r) {
	if (vl == l && vr == r) {
		return t[v];
	}
	int m = (vl + vr) / 2;
	int res = 1;
	if (l <= m)res = min(res, Mn(v * 2, vl, m, l, min(m, r)));
	if (r > m)res = min(res, Mn(v * 2 + 1, m + 1, vr, max(l, m + 1), r));
	return res;
}
void SortedSolve(int n, int m) {
	for (int i = 1; i < n; i++)
		diff[i] = w[i] - w[i - 1];
	Buildsegtree(1, 1, n - 1);
	for (int q = 0; q < m; q++) {
		int ql = query[q].l, qr = query[q].r;
		if (ql != qr && Mn(1, 1, n - 1, ql + 1, qr) < 0)query[q].ans = 0;
		else query[q].ans = 1;
	}
}
void Build(int n)
{
	lg[1] = 0;
	for (int i = 2; i <= n; i++)
		lg[i] = lg[i / 2] + 1;
	int k = lg[n];
	for (int i = 0; i < n; i++)
		mx[i][0] = w[i];
	for (int j = 1; j <= k; j++)
		for (int i = 0; i + (1 << j) - 1 <= n; i++)
			mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
}
int Mx(int l, int r)
{
	int j = lg[r - l + 1];
	return max(mx[l][j], mx[r - (1 << j) + 1][j]);
}
int main()
{
	for (int i = 0; i < 1001; i++)
		p[i] = -1;
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> w[i];
		if (w[i] > 1000)f = false;
	}
	for (int i = 0; i < m; i++) {
		cin >> query[i].l >> query[i].r >> query[i].k;
		query[i].l--; query[i].r--;
		query[i].ind = i;
	}
	if (n <= 5000 && m <= 5000) {
		PoqrSolve(n, m);
	}
	else if (f) {
		Build(n);
		for (int i = 0; i < n; i++)
			prv[w[i]].push_back(i);
		sort(query, query + m);
		for (int q = 0; q < m; q++)
		{
			bool ok = true;
			for (int i = 0; i <= 1000; i++)
			{
				while (!prv[i].empty() && p[i] + 1 < prv[i].size() && prv[i][p[i] + 1] <= query[q].r)
					p[i]++;
				if (p[i] == -1)continue;
				int tmp;
				if (prv[i][p[i]] >= query[q].l && (tmp = Mx(query[q].l, prv[i][p[i]])) > i) {
					if (tmp + i > query[q].k)ok = false;
				}
			}
			if (ok)query[q].ans = 1;
		}
		sort(query, query + m, het);
	}
	else {
		Build(n);
		SortedSolve(n, m);
	}
	for (int i = 0; i < m; i++)
		cout << query[i].ans << '\n';
	return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:116:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     while (!prv[i].empty() && p[i] + 1 < prv[i].size() && prv[i][p[i] + 1] <= query[q].r)
      |                               ~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 6 ms 492 KB Output is correct
14 Correct 8 ms 492 KB Output is correct
15 Correct 8 ms 492 KB Output is correct
16 Correct 18 ms 492 KB Output is correct
17 Correct 18 ms 492 KB Output is correct
18 Correct 15 ms 492 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2430 ms 120172 KB Output is correct
2 Correct 2485 ms 123656 KB Output is correct
3 Correct 2516 ms 126504 KB Output is correct
4 Correct 2523 ms 121420 KB Output is correct
5 Correct 2479 ms 121300 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1630 ms 11848 KB Output is correct
2 Correct 1442 ms 11984 KB Output is correct
3 Correct 1048 ms 12012 KB Output is correct
4 Correct 928 ms 11964 KB Output is correct
5 Correct 841 ms 11908 KB Output is correct
6 Correct 1650 ms 11908 KB Output is correct
7 Correct 1590 ms 11912 KB Output is correct
8 Correct 366 ms 11880 KB Output is correct
9 Correct 486 ms 2924 KB Output is correct
10 Correct 359 ms 11880 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 6 ms 492 KB Output is correct
14 Correct 8 ms 492 KB Output is correct
15 Correct 8 ms 492 KB Output is correct
16 Correct 18 ms 492 KB Output is correct
17 Correct 18 ms 492 KB Output is correct
18 Correct 15 ms 492 KB Output is correct
19 Correct 2430 ms 120172 KB Output is correct
20 Correct 2485 ms 123656 KB Output is correct
21 Correct 2516 ms 126504 KB Output is correct
22 Correct 2523 ms 121420 KB Output is correct
23 Correct 2479 ms 121300 KB Output is correct
24 Correct 1630 ms 11848 KB Output is correct
25 Correct 1442 ms 11984 KB Output is correct
26 Correct 1048 ms 12012 KB Output is correct
27 Correct 928 ms 11964 KB Output is correct
28 Correct 841 ms 11908 KB Output is correct
29 Correct 1650 ms 11908 KB Output is correct
30 Correct 1590 ms 11912 KB Output is correct
31 Correct 366 ms 11880 KB Output is correct
32 Correct 486 ms 2924 KB Output is correct
33 Correct 359 ms 11880 KB Output is correct
34 Incorrect 470 ms 25228 KB Output isn't correct
35 Halted 0 ms 0 KB -