Submission #344684

#	Time	Username	Problem	Language	Result	Execution time	Memory
344684		_ani	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	47 / 100	2523 ms	126504 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];
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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23