Submission #1096627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096627		rayan_bd	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3062 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

#define getar(ar,n) for(ll i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
#define nl '\n'
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ret return
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())

const int mxN = 1e6 + 50;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ld EPS = 1e-9;

struct Node {
    vector<ll> vec;
    ll mx = 0, bad_mx = 0;
};
Node seg[mxN * 4];
ll ar[mxN];

Node dummy_node;

ll calc1(ll node) {
    ll lft_max = seg[node * 2 + 1].mx;
    
    auto it = upper_bound(all(seg[node * 2 + 2].vec), lft_max);
    
    if (it == seg[node * 2 + 2].vec.begin()) {
        return -lft_max; 
    } else {
        --it;
        return *it + lft_max;
    }
}

Node left_right_mrg(Node lft, Node rgt) {
    ll lft_max = lft.mx;
    
    auto it = upper_bound(all(rgt.vec), lft_max);
    ll ans = -lft_max;
    
    if (it != rgt.vec.begin()) {
        --it;
        ans = *it + lft_max;
    }
    
    Node curr;
    curr.bad_mx = max({lft.bad_mx, ans, rgt.bad_mx});
    merge(all(lft.vec), all(rgt.vec), back_inserter(curr.vec));
    curr.mx = max(lft.mx, rgt.mx);

    return curr;
}

void build(ll node, ll start, ll end) {
    if (start == end) {
        seg[node].vec.pb(ar[start]);
        seg[node].mx = ar[start];
        seg[node].bad_mx = 0;
        return;
    }
    ll mid = start + (end - start) / 2;
    build(node * 2 + 1, start, mid);
    build(node * 2 + 2, mid + 1, end);

    merge(all(seg[node * 2 + 1].vec), all(seg[node * 2 + 2].vec), back_inserter(seg[node].vec));
    seg[node].bad_mx = max({seg[node * 2 + 1].bad_mx, seg[node * 2 + 2].bad_mx, calc1(node)});
    seg[node].mx = max(seg[node * 2 + 1].mx, seg[node * 2 + 2].mx);
}

Node qry(ll nd, ll start, ll end, ll l, ll r) {
    if (start > r || end < l) return dummy_node;
    if (start >= l && end <= r) return seg[nd];
    ll mid = start + (end - start) / 2;
    Node lft = qry(nd * 2 + 1, start, mid, l, r);
    Node rgt = qry(nd * 2 + 2, mid + 1, end, l, r);
    if (lft.mx == -1) return rgt;
    else if (rgt.mx == -1) return lft;
    return left_right_mrg(lft, rgt);
}

void solve() {
    ll n, l, r, w, q;
    cin >> n >> q;
    for (ll i = 0; i < n; ++i) {
        cin >> ar[i];
    }
    dummy_node.mx = -1;
    build(0, 0, n - 1);
    while (q--) {
        cin >> l >> r >> w;
        cout << (qry(0, 0, n - 1, l - 1, r - 1).bad_mx <= w) << nl;
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

sortbooks.cpp:25:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   25 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
sortbooks.cpp:32:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
sortbooks.cpp:34:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   34 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
sortbooks.cpp:48:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   48 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
sortbooks.cpp:79:17: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   79 | ll calc1(ll node) {
      |                 ^
sortbooks.cpp:79:17: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:79:17: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:79:17: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:92:39: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   92 | Node left_right_mrg(Node lft, Node rgt) {
      |                                       ^
sortbooks.cpp:92:39: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:92:39: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:92:39: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:111:37: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  111 | void build(ll node, ll start, ll end) {
      |                                     ^
sortbooks.cpp:111:37: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:111:37: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:111:37: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:127:45: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  127 | Node qry(ll nd, ll start, ll end, ll l, ll r) {
      |                                             ^
sortbooks.cpp:127:45: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:127:45: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:127:45: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:138:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  138 | void solve() {
      |            ^
sortbooks.cpp:138:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:138:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:138:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:152:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  152 | signed main() {
      |             ^
sortbooks.cpp:152:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:152:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:152:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]

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