Submission #384761

#	Time	Username	Problem	Language	Result	Execution time	Memory
384761		ritul_kr_singh	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1436 ms	110524 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

struct SegmentTree{
	vector<int> a; int sz = 1, ID = -1e18;
	SegmentTree(vector<int> &v){
		while(sz < (int)v.size()) sz += sz;
		a.assign(2*sz, ID);
		build(v, 0, 0, sz);
	}
	void build(vector<int> &v, int x, int lx, int rx){
		if(rx-lx==1){
			if(lx < (int)v.size()) a[x] = v[lx];
			return;
		}
		int mx = (lx+rx)/2;
		build(v, 2*x+1, lx, mx);
		build(v, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int val, int x, int lx, int rx){
		if(rx-lx==1) return void(a[x] = val);
		int mx = (lx+rx)/2;
		if(i < mx) update(i, val, 2*x+1, lx, mx);
		else update(i, val, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int val){ update(i, val, 0, 0, sz); }
	int get(int l, int r, int x, int lx, int rx){
		if(r<=lx or rx<=l) return ID;
		if(l<=lx and rx<=r) return a[x];
		int mx = (lx+rx)/2;
		return max(get(l, r, 2*x+1, lx, mx), get(l, r, 2*x+2, mx, rx));
	}
	int get(int r){ return get(0, r+1, 0, 0, sz); }
};

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m; cin >> n >> m;
	int a[n]; for(int &i : a) cin >> i;

	vector<int> closest(n, -1), s, sum(n, -1e18);
	vector<pair<int, int>> byLeft;
	for(int i=0; i<n; ++i){
		while(!s.empty() and a[s.back()] <= a[i]) s.pop_back();
		if(!s.empty()){
			closest[i] = s.back();
			sum[i] = a[i] + a[s.back()];
			byLeft.emplace_back(s.back(), i);
		}
		s.push_back(i);
	}
	SegmentTree st(sum);
	sort(byLeft.rbegin(), byLeft.rend());
	array<int, 4> q[m];
	bool ans[m];
	for(int i=0; i<m; ++i){
		cin >> q[i][0] >> q[i][1] >> q[i][2];
		q[i][3] = i;
		--q[i][0], --q[i][1];
	}
	sort(q, q+m);
	for(auto &i : q){
		while(!byLeft.empty() and byLeft.back().first < i[0]){
			st.update(byLeft.back().second, -1e18);
			byLeft.pop_back();
		}
		ans[i[3]] = st.get(i[1]) <= i[2];
	}
	for(auto i : ans) cout << i nl;
}

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