Submission #1116512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116512		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1143 ms	118132 KiB

sortbooks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>


using namespace std;
using namespace __gnu_pbds;

template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
#define all(v) v.begin(), v.end()
#define int long long
#define ld long double
#define ll long double
#define ar array

mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e6 + 20;
const int M = (1 << 14) + 10;

const int LOG = __lg(N) + 2;
const int SQRT = sqrt(N);

//const int MOD = 998244353;
const int MOD = 1e9 + 7;
const int INF = 1e16;
const ld EPS = 1e-12;
const ld PI = 3.14159265358979323846;

int n, m, k, q, l, r, x, y, z;
int ans;

void orz();

signed main(){
	send help;
	int t = 1;
	//cin>>t;
	while(t--)orz();
}

namespace seggy{
	int s[4 * N];
	
	void upd(int k,int tl,int tr,int p,int v){
		if(tl == tr){
			s[k] = max(s[k], v);
			return;
		}
		int tm = (tl + tr) / 2;
		if(p <= tm)upd(k * 2, tl, tm, p, v);
		else upd(k * 2 + 1, tm + 1, tr, p, v);
		s[k] = max(s[k * 2], s[k * 2 + 1]);
	}
	
	int qry(int k,int tl,int tr,int l,int r){
		if(tl > r || l > tr)return -INF;
		if(l <= tl && tr <= r)return s[k];
		int tm = (tl + tr) / 2;
		return max(qry(k * 2, tl, tm, l, r), qry(k * 2 + 1,tm + 1, tr, l, r));
	}
};

int A[N];

void orz(){
	cin>>n>>m;
	for(int i = 0;i < n;i++)cin>>A[i];
	
	vector<ar<int, 3> > que[n];
	for(int i = 0;i < m;i++){
		int l, r, x;
		cin>>l>>r>>x;
		--l, --r;
		que[r].push_back({l, x, i});
	}
	bool ans[m];
	stack<int> st;
	for(int i = 0;i < n;i++){
		while(st.size() && A[st.top()] <= A[i])st.pop();
		if(st.size())seggy::upd(1, 0, n - 1, st.top(), A[st.top()] + A[i]);
		for(auto [l, x, j]: que[i])ans[j] = seggy::qry(1, 0, n - 1, l, i) <= x;
		st.push(i);
	}
	for(auto u: ans)cout<<u<<'\n';
	
}

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