Submission #520897

#	Time	Username	Problem	Language	Result	Execution time	Memory
520897		shmad	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	13 / 100	1140 ms	108388 KiB

sortbooks

#pragma GCC optimize("O3", "unroll-loops") // "Ofast"
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") 

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vvi = vt< vt<int> >;         

const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 60);
const double eps = 1e-6;

struct Event {
	int l, r, k;
};

vt<Event> g[N];
int n, m, t[4 * N], w[N], ans[N], L[N];
stack<int> s;

void upd (int pos, int val, int x = 1, int tl = 1, int tr = n) {
	if (tl == tr) {
		t[x] = max(t[x], val);
		return;
	}
	int tm = tl + tr >> 1, v = x + 1, u = x + ((tm - tl + 1) << 1);
	if (pos <= tm) upd(pos, val, v, tl, tm);
	else upd(pos, val, u, tm + 1, tr);
	t[x] = t[v] + t[u];
}

int get (int l, int r, int x = 1, int tl = 1, int tr = n) {
	if (tl > r || tr < l) return 0;
	if (tl >= l && tr <= r) return t[x];
	int tm = tl + tr >> 1, v = x + 1, u = x + ((tm - tl + 1) << 1);
	int a = get(l, r, v, tl, tm);
	int b = get(l, r, u, tm + 1, tr);
	return max(a, b);
}

void solve () {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> w[i];
	for (int q = 1; q <= m; q++) {
		int l, r, k;
		cin >> l >> r >> k;
		g[r].pb({l, k, q});
	}
	for (int i = 1; i <= n; i++) {
		L[i] = i;
		while (!s.empty() && w[s.top()] <= w[i]) {
			L[i] = L[s.top()];
			s.pop();
		}
		s.push(i);
	}
	for (int i = 1; i <= n; i++) {
		int j = L[i] - 1;
		if (j) upd(j, w[i] + w[j]);
		for (auto [l, k, id]: g[i]) ans[id] = (get(l, n) <= k);
	}
	for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
	cout << '\n';
}

bool testcases = 0;
                  
signed main() {
#ifdef ONLINE_JUDGE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
    cin.tie(0) -> sync_with_stdio(0);
    int test = 1;
    if (testcases) cin >> test;
    for (int cs = 1; cs <= test; cs++) {
        solve();
    }
}

Compilation message (stderr)

sortbooks.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:36:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |  int tm = tl + tr >> 1, v = x + 1, u = x + ((tm - tl + 1) << 1);
      |           ~~~^~~~
sortbooks.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  int tm = tl + tr >> 1, v = x + 1, u = x + ((tm - tl + 1) << 1);
      |           ~~~^~~~

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