Submission #344469

#	Time	Username	Problem	Language	Result	Execution time	Memory
344469		_ani	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	34 / 100	1836 ms	262148 KiB

sortbooks

#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];
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 SortedSolve(int n, int m) {
	int l = 0, r = 0;
	while (l < n)
	{
		while (r + 1 < n && w[r + 1] >= w[r])
			r++;
		s.push_back({ l,r });
		l = r + 1;
	}
	sort(s.begin(), s.end());
	for (int q = 0; q < m; q++) {
		int ql = query[q].l, qr = query[q].r;
		int l = 0, r = (int)s.size() - 1;
		bool ok = false;
		while (l <= r)
		{
			int m = l + (r - l) / 2;
			if (s[m].first <= ql && s[m].second >= qr)
			{
				ok = true;
				break;
			}
			if (s[m].first <= ql)
				l = m + 1;
			else r = m - 1;
		}
		if (!ok)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 (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23