Submission #889954

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
889954	2023-12-20T10:17:58 Z	vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	13 / 100	1014 ms	59216 KB

sortbooks

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define forik(x) ll i = 1; i <= x; i++

// (a mod 1e9) / (b mod 1e9) = a * (b^1e9)

using namespace std;

ll a, b, c, d, e, f, n, m, k, p[1000001], l, md[8000001];
pair <ll, ll> t[8000001];

pair <ll, ll> qw (pair <ll, ll> a, pair <ll, ll> b){
//	cout << a.F << ' ' << a.S << ' ' << b.F << ' ' << b.S << '\n';
	if (a.F == -1 && b.F == -1){
		return {-1, -1};
	}
	if (b.F == -1){
		return a;
	}
	if (a.F == -1){
		return b;
	}
	if (a.S > b.F){
		d = max (d, a.S + b.F);
	}
	if (a.S > b.S){
		d = max (d, a.S + b.S);
	}
	return {min (a.F, b.F), max (b.S, a.S)};
}

void build (ll tl = 1, ll tr = n, ll v = 1){
	if (tl == tr){
		t[v] = {p[tl], p[tl]};
		return;
	}
	ll tm = (tl + tr) / 2;
	build (tl, tm, v * 2);
	build (tm + 1, tr, v * 2 + 1);
	if (t[v * 2].S > t[v * 2 + 1].F){
		md[v] = t[v * 2 + 1].F + t[v * 2].S;
	}
	t[v] = {min (t[v * 2].F, t[v * 2 + 1].F), max (t[v * 2].S, t[v * 2 + 1].S)};
}

pair <ll, ll> get (ll l, ll r, ll tl = 1, ll tr = n, ll v = 1){
	if (l <= tl && tr <= r){
		d = max (d, md[v]);
		return t[v];
	}
	if (tl > r || l > tr){
		return {-1, -1};
	}
	ll tm = (tl + tr) / 2;
	return qw (get (l, r, tl, tm, v * 2), get (l, r, tm + 1, tr, v * 2 + 1));
}

signed main (){
	//freopen (".in", "r", stdin);
	//freopen (".out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> p[i];
	}
	build ();
	while (m--){
		cin >> a >> b >> c;
		d = 0;
		pair <ll, ll> ans = get (a, b);
		if (d > c){
			cout << "0\n";
		}
		else{
			cout << "1\n";
		}
	}
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:81:17: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   81 |   pair <ll, ll> ans = get (a, b);
      |                 ^~~

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Incorrect	1 ms	4444 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Incorrect	1 ms	4444 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1006 ms	54544 KB	Output is correct
2	Correct	1014 ms	59216 KB	Output is correct
3	Correct	998 ms	58604 KB	Output is correct
4	Correct	1008 ms	58832 KB	Output is correct
5	Correct	913 ms	48800 KB	Output is correct