Submission #1005520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005520		ByeWorld	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	34 / 100	611 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
// #define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e6+10;
const int INF = 1e9+10;
const int LOG = 29;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};

int n, m, q;
int a[MAXN];

struct seg {
	set <int> st[3*MAXN]; int val[3*MAXN];
	void mrg(int id){
		for(auto in : st[lf]) st[id].insert(in);
		for(auto in : st[rg]) st[id].insert(in);
		val[id] = max(val[lf], val[rg]);

		int le = *(--st[lf].end());
		auto it = st[rg].lower_bound(le);
		if(it != st[rg].begin()){
			it--; 
			val[id] = max(val[id], le + *(it));
		}
	}
	void bd(int id, int l, int r){
		if(l==r){ st[id].insert(a[l]); val[id] = -INF; return; }
		bd(lf, l, md); bd(rg, md+1, r);
		mrg(id);
	}
	int que(int id, int l, int r, int x, int y){
		if(r<x || y<l) return -INF;
		if(x<=l && r<=y) return *(--st[id].end());
		return max(que(lf, l, md, x, y), que(rg, md+1, r, x, y));
	}
	int find(int id, int l, int r, int x, int y){
		if(r<x || y<l) return -INF;
		if(x<=l && r<=y){
			int bef = que(1, 1, n, x, l-1); // mx di sebelum
			int aft = -INF;
			auto it = st[id].lower_bound(bef);
			if(it != st[id].begin()){
				it--; 
				aft = *(it);
			}

			return max(val[id], bef+aft);
		}
		int MX = max(find(lf, l, md, x, y), find(rg, md+1, r, x, y));

		// int bef = que(1, 1, n, x, l-1), aft = -INF;
		// auto it = st[rg].lower_bound(bef);
		// if(it != st[rg].begin()){
		// 	it--; 
		// 	aft = *(it);
		// }
		return MX;
	}
} A;

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i=1; i<=n; i++) cin >> a[i];
	A.bd(1, 1, n);

	for(int xx=1; xx<=m; xx++){
		int l, r, x; cin >> l >> r >> x;
		cout << (A.find(1, 1, n, l, r) <= x) << '\n';
	}
}

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