Submission #560672

#	Time	Username	Problem	Language	Result	Execution time	Memory
560672		aryan12	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1416 ms	162112 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e6 + 5;
vector<int> a(N), val(N, -1);
vector<array<int, 2> > g[N];
int seg[N * 4];

void Update(int l, int r, int pos, int qpos, int qval)
{
	seg[pos] = max(seg[pos], qval);
	if(l == r)
	{
		return;
	}
	int mid = (l + r) >> 1;
	if(qpos <= mid) Update(l, mid, pos * 2, qpos, qval);
	else Update(mid + 1, r, pos * 2 + 1, qpos, qval);
}

int Query(int l, int r, int pos, int ql, int qr)
{
	if(ql <= l && r <= qr)
	{
		return seg[pos];
	}
	if(ql > r || l > qr)
	{
		return 0;
	}
	int mid = (l + r) >> 1;
	return max(Query(l, mid, pos * 2, ql, qr), Query(mid + 1, r, pos * 2 + 1, ql, qr));
}

struct query
{
	int l, r, idx, ans, value;
};

vector<query> queries(N);

bool cmp(query x, query y)
{
	if(x.r != y.r)
	{
		return x.r < y.r;
	}
	return x.l < y.l;
}

bool cmp2(query x, query y)
{
	return x.idx < y.idx; 
}

void Solve() 
{
	int n, q;
	cin >> n >> q;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for(int i = 1; i <= q; i++)
	{
		cin >> queries[i].l >> queries[i].r >> queries[i].value;
		queries[i].idx = i;
		queries[i].ans = 0;
	}
	stack<pair<int, int> > s;
	s.push({val[1], 1});
	for(int i = 2; i <= n; i++)
	{
		while(!s.empty() && s.top().first <= a[i])
		{
			s.pop();
		}
		if(!s.empty())
		{
			val[i] = s.top().second;
		}
		s.push({a[i], i});
	}
	for(int i = 1; i <= n; i++)
	{
		if(val[i] != -1)
		{
			// cout << i << " -> " << val[i] << ", with wt -> " << a[val[i]] + a[i] << "\n";
			g[i].push_back({val[i], a[val[i]] + a[i]});
		}
	}
	sort(queries.begin() + 1, queries.begin() + 1 + q, cmp);
	int pos = 1;
	for(int i = 1; i <= n; i++)
	{
		for(auto [to, wt]: g[i])
		{
			Update(1, n, 1, to, wt);
		}
		while(pos != q + 1 && queries[pos].r == i)
		{
			// cout << "pos = " << pos << ", idx = " << queries[pos].idx << "\n";
			queries[pos].ans = Query(1, n, 1, queries[pos].l, queries[pos].r);
			// cout << "queries[i].ans = " << queries[pos].ans << "\n";
			// cout << "queries[i].l = " << queries[pos].l << ", queries[i].r = " << queries[pos].r << "\n";
			pos++;
		}
	}
	sort(queries.begin() + 1, queries.begin() + 1 + q, cmp2);
	for(int i = 1; i <= q; i++)
	{
		// cout << "queries[i].ans = " << queries[i].ans << "\n";
		if(queries[i].ans <= queries[i].value)
		{
			cout << "1\n";
		}
		else
		{
			cout << "0\n";
		}
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

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