Submission #889877

#	Time	Username	Problem	Language	Result	Execution time	Memory
889877		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	30 / 100	841 ms	144588 KiB

sortbooks

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define forik(x) ll i = 1; i <= x; i++

// (a mod 1e9) / (b mod 1e9) = a * (b^1e9)

using namespace std;

ll a, b, c, e, f, t[8000001], n, m, k, p[1000001], d[5001][5001];
vector <pair <ll, ll>> g;

void upd (ll idx, ll val, ll tl = 1, ll tr = n, ll v = 1){
	if (tl > idx || tr < idx){
		return;
	}
	if (tl == tr && tr == idx){
		t[v] = val;
		return;
	}
	ll tm = (tl + tr) / 2;
	upd (idx, val, tl, tm, v * 2);
	upd (idx, val, tm + 1, tr, v * 2 + 1);
	t[v] = t[v * 2 + 1] + t[v * 2];
}

ll get (ll l, ll r, ll tl = 1, ll tr = n, ll v = 1){
	if (tl >= l && tr <= r){
		return t[v];
	}
	if (tl > r || l > tr){
		return 0;
	}
	ll tm = (tl + tr) / 2;
	return get (l, r, tl, tm, v * 2) + get (l, r, tm + 1, tr, v * 2 + 1);
}

signed main (){
	//freopen (".in", "r", stdin);
	//freopen (".out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> p[i];
	}
	if (n <= 5000 && m <= 5000){
		for (int i = 1; i <= n; i++){
			a = p[i];
			for (int y = i + 1; y <= n; y++){
				d[i][y] = d[i][y - 1];
				a = max (a, p[y]);
				if (a > p[y]){
					d[i][y] = max (d[i][y], a + p[y]);
				}
			}	
		}
		while (m--){
			cin >> a >> b >> c;
			e = 1;
			if (d[a][b] > c){
				e = 0;
			}
			cout << e << '\n';
		}	
	}
	else{
		a = p[1];
		for (int i = 1; i <= n; i++){
			if (a > p[i]){
				upd (i, 1);
			}
			a = p[i];
		}
		while (m--){
			cin >> a >> b >> c;
			if (a == b){
				cout << 1 << '\n';
				continue;
			}
			if (get (a + 1, b) > 0){
				cout << "0\n";
			}
			else{
				cout << "1\n";
			}
		}
	}
}

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