Submission #480037

#	Time	Username	Problem	Language	Result	Execution time	Memory
480037		levsog2004	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3061 ms	58444 KiB

sortbooks

#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef  int ll;
#define all(x) x.begin(),x.end()
#define al(a,n)  (a,a+n)
#define se second
#define fr first
#define m_p make_pair
const ll N = 2000004;
const ll mod = 1000 * 1000 * 1000 + 7;
const ll inf = 1000000000;
ll n, m, k, z, t, ans, x,y, pat,a[N];
int main()
{

	cin >> n >> m;
	k = m;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	map <ll, ll> mp;
	int j = 0;
	for (int i = 0; i < n; ++i)
	{
		j = max(j, i);
		while (j < n - 1 && a[j] <= a[j + 1])
			++j;
		mp[i] = j;
	}
	while (m--)
	{
		cin >> x >> y >> z;
		x--;
		y--;
		if (n*k > 25000000)
		{
			if (mp[x] < y)
				cout << 0 << endl;
			else
				cout << 1 << endl;
		}
		else
		{
			vector<ll> v;
			for (int i = x; i <= y; ++i)
			{
				v.push_back(a[i]);
			}
			sort(all(v));
			ll p = 0;
			for (int i = v.size() - 1; i >= 0; --i)
			{
				if (v[i] != a[i])
				{
					p = v[i];
					break;
				}
			}
			if (v[0] + p > z)
				cout << 0 << endl;
			else
				cout << 1 << endl;
		}
	}
		return 0;
}

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