Submission #1014683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014683		jcelin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	833 ms	98296 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int arr[MAXN];

struct tournament{
	int seg[trsz];
	
	void update(int x, int vl){
		x += off;
		seg[x] = max(seg[x], vl);
		for(x /= 2; x; x /= 2) seg[x] = max(seg[x], vl);
	}
	
	int query(int l, int r){
		int ret = 0;
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) ret = max(ret, seg[l++]);
			if(r & 1) ret = max(ret, seg[--r]);
		}
		return ret;
	}
}t;

vii st, qs[MAXN];
int ans[MAXN], lim[MAXN];

void solve(){
	int n, m;
	cin >> n >> m;
	for(int i=1; i<=n; i++) cin >> arr[i];
	st.PB({0, inf});
	for(int i=0; i<m; i++){
		int l, r;
		cin >> l >> r >> lim[i];
		qs[r].PB({l, i});
	}
	
	
	for(int i=1; i<=n; i++){
		while(st.back().Y <= arr[i]) st.PPB();
		t.update(st.back().X, st.back().Y + arr[i]);
		st.PB({i, arr[i]});
		for(auto &x : qs[i]){
			ans[x.Y] = (lim[x.Y] >= t.query(x.X, i + 1));
		}
	}
	
	
	for(int i=0; i<m; i++) cout << ans[i] << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while(tt--) solve();
	return 0;
}

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