Submission #343354

#	Time	Username	Problem	Language	Result	Execution time	Memory
343354		jenkinsser	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1012 ms	71952 KiB

sortbooks

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define N 1000005
#define INF 1e9+5
#define sp " "
#define endl "\n"
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define all(x) (x).begin(),(x).end()
#define ll long long
using namespace std;

int a[N], ans[N];

vector<pair<pii,int>> q[N];

int f[N];
void upd(int i, int j) {
	i = N - 1 - i;
	while (i < N) {
		f[i] = max(f[i], j);
		i |= i + 1;
	}
}
int get(int i) {
	i = N - 1 - i;
	int j = 0;
	while (i >= 0) {
		j = max(j, f[i]);
		i &= i + 1;
		i--;
	}
	return j;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1 ; i <= n ; ++ i) cin >> a[i];
	for (int i = 1 ; i <= m ; ++ i) {
		int l, r, k;
		cin >> l >> r >> k;
		q[r].push_back({{l, k}, i});
	}
	stack<int> s;
	for (int i = 1 ; i <= n ; ++ i) {
		while (s.size() && a[s.top()] <= a[i]) s.pop();
		if (s.size()) {
			int j = s.top();
			upd(j, a[i] + a[j]);
		}
		s.push(i);
		for (int j=0;j<q[i].size();j++) {
            pair<pii,int> p=q[i][j];
			ans[p.nd] = (get(p.st.st) <= p.st.nd);
		}
	}
	for (int i = 1 ; i <= m ; ++ i) cout << ans[i] << "\n";
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int j=0;j<q[i].size();j++) {
      |                ~^~~~~~~~~~~~

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