Submission #1124870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124870		zhasyn	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	64 / 100	3101 ms	173648 KiB

sortbooks

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1e6 + 100, M = 500 + 10, len = 315, inf = 1e18;
const ll mod = 998244353;
ll um(ll a, ll b){
	return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
ll bp(ll x, ll step){
	ll res = 1;
	while(step){
		if(step & 1) res = um(res, x);
		x = um(x, x);
		step /= 2;
	}
	return res;
}
ll inv(ll x){
	return bp(x, mod - 2);
}
ll arr[N], b[N];
// work with indexes
struct segtree{
	vector <ll> tree, num, ans;
	vector <pair <ll, ll>> mx;
	ll sz;
	void init(ll n){
		sz = 1;
		while(sz < n) sz *= 2;
		tree.assign(n * 4, LLONG_MAX);
		num.assign(n * 4, 0LL);
		ans.assign(n * 4, 0LL);
		mx.assign(n * 4, {0LL, 0});
	}
	void upd(ll v, ll i, ll x, ll lx, ll rx, ll code){
		if(rx - lx == 1){
			if(code == 1) tree[x] = v;
			if(code == 2) num[x] = v;
			if(code == 3) ans[x] = v;
			if(code == 4) mx[x] = {v, i};
			return;
		}
		ll mid = (rx + lx) / 2;
		if(i < mid) upd(v, i, 2 * x + 1, lx, mid, code);
		else upd(v, i, 2 * x + 2, mid, rx, code);
		if(code == 1) tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
		if(code == 2) num[x] = max(num[2 * x + 1], num[2 * x + 2]);
		if(code == 3) ans[x] = max(ans[2 * x + 1], ans[2 * x + 2]);
		if(code == 4){
			if(mx[2 * x + 2].F >= mx[2 * x + 1].F) mx[x] = mx[2 * x + 2];
			else mx[x] = mx[2 * x + 1];
		}
	}
	void upd(ll v, ll i, ll code){
		upd(v, i, 0, 0, sz, code);
	}
	
	pll getp(ll l, ll r, ll x, ll lx, ll rx){
		if(lx >= r || l >= rx){
			return {-1LL, 0LL};
		}
		if(l <= lx && rx <= r){
			return mx[x];
		}
		ll mid = (rx + lx) / 2;
		pll s1 = getp(l, r, 2 * x + 1, lx, mid);
		pll s2 = getp(l, r, 2 * x + 2, mid, rx);
		//cout << s1.F << " " << s1.S << endl;
		//cout << s2.F << " " << s2.S << endl;
		//cout << endl;
		if(s2.F >= s1.F) return s2;
		else return s1;
	}
	pll getp(ll l, ll r){
		return getp(l, r, 0, 0, sz);
	}
	
	ll get(ll l, ll r, ll x, ll lx, ll rx, ll code){
		if(lx >= r || l >= rx){
			if(code == 1) return LLONG_MAX;
			if(code == 2) return 0LL;
			if(code == 3) return 0LL;
		}
		if(l <= lx && rx <= r){
			if(code == 1) return tree[x];
			if(code == 2) return num[x];
			if(code == 3) return ans[x];
		}
		ll mid = (rx + lx) / 2;
		ll s1 = get(l, r, 2 * x + 1, lx, mid, code);
		ll s2 = get(l, r, 2 * x + 2, mid, rx, code);
		if(code == 1) return min(s1, s2);
		if(code == 2) return max(s1, s2);
		return max(s1, s2);
	}
	ll get(ll l, ll r, ll code){
		return get(l, r, 0, 0, sz, code);
	}
	ll get_mx(ll l, ll code){
		return get(l, sz, 0, 0, sz, code);
	}
};
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	ll n, d;
	cin >> n >> d;
	for(ll i = 0; i < n; i++){
		cin >> arr[i];
		b[i] = arr[i];
	}
	sort(b, b + n);
	ll sz = unique(b, b + n) - b;
	segtree obj;
	obj.init(n + 10);
	
	for(ll i = 0; i < n; i++){
		arr[i] = lower_bound(b, b + sz, arr[i]) - b;
		obj.upd(arr[i], i, 2);
		obj.upd(arr[i], i, 4);
	}
	
	
	for(ll i = n - 1; i >= 0; i--){
		if(i != n - 1){
			ll res = obj.get_mx(arr[i], 1);
			if(res == LLONG_MAX) obj.upd(b[arr[i]] + b[obj.get_mx(i + 1, 2)], i, 3);
			else{
				if(res == i + 1) obj.upd(0LL, i, 3);
				else obj.upd(b[arr[i]] + b[obj.get(i + 1, res, 2)], i, 3);
			}
		}
		obj.upd(i, arr[i], 1);
	}
	for(ll i = 0, l, r, k; i < d; i++){
		cin >> l >> r >> k;
		l--;
		
		pll pos = obj.getp(l, r);
		ll res1 = obj.get(l, pos.S, 3), res2;
		if(pos.S == r - 1) res2 = 0;
		else{
			res2 = b[pos.F] + b[obj.get(pos.S + 1, r, 2)];
		}
		if(max(res1, res2) > k) cout << 0 << endl;
		else cout << 1 << endl;
	}
  return 0;
}

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