Submission #1136889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136889		SSSM	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	104 ms	129684 KiB

sortbooks

#include <bits/stdc++.h>

/*
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx2")
*/

using namespace std;

/*
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define F first
#define S second
#define pb push_back
#define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
#define md(a) ((a%mod+mod)%mod)
#define all(a) a.begin(), a.end()
#define MP make_pair
#define lc (id<<1)
#define rc (lc|1)
#define mid (l+r)/2
#define kill(a) cout << a << "\n", exit(0)
#define SZ(a) (ll)a.size()
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
mt19937_64  rng(chrono::steady_clock::now().time_since_epoch().count());

ll const maxn=1e6+10, mod=1e9+7, INF=1e18, LOG=60, sq=65;

ll poww(ll a, ll b, ll mod) {
 if (b == 0) return 1;
 return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod;
}

struct Node{
    int ans;
    vector<int> vec;
    Node(int ans_, vector<int> vec_)
    {
        ans=ans_;
        vec=vec_;
    }
    Node () {};

} seg[maxn<<2];
int n, q, A[maxn];

Node Merge(Node L, Node R)
{
    if(!SZ(L.vec)) return R;
    if(!SZ(R.vec)) return L;
    vector<int> vec;
    for(int j:L.vec) vec.pb(j);
    for(int j:R.vec) vec.pb(j);
    sort(all(vec));
    int ans=max(L.ans, R.ans);
    int t=lower_bound(all(R.vec), L.vec.back())-vec.begin();
    if(t!=0) ans=max(ans, L.vec.back()+(R.vec[t-1]));
    return Node(ans, vec);
    return L;
}

void Build(int l=1, int r=n+1, int id=1)
{
    if(l==r-1)
    {
        seg[id]=Node(0, vector<int>{A[l]});
        return;
    }
    Build(l, mid, lc);
    Build(mid, r, rc);
    seg[id]=Merge(seg[lc], seg[rc]);
}

Node Get(int s, int e, int l=1, int r=n+1, int id=1)
{
    if(l>=e || r<=s) return Node(0, vector<int>{});
    if(s<=l && r<=e) return seg[id];
    return Merge(Get(s, e, l, mid, lc), Get(s, e, mid, r, rc));
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>A[i];
    Build();
    while(q--)
    {
        int l, r, k;
        cin>>l>>r>>k;
        Node nd=Get(l, r+1);
        if(nd.ans<=k) cout<<1<<"\n";
        else cout<<"0\n";
    }
}

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