Submission #487536

#	Time	Username	Problem	Language	Result	Execution time	Memory
487536		freddy645645	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	988 ms	98924 KiB

sortbooks

#include <bits/stdc++.h>
#include <bits/extc++.h>

//#define double long double
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(nullptr);
#define pb push_back
#define UNIQUE(a) sort(ALL(a));a.resize(unique(ALL(a))-a.begin());
#define ALL(X) X.begin(),X.end()
#define F(i,n)  FF(i,0,(n))
#define F1(i,n)  FF(i,1,(n)+1)
#define FF(i,n,m) for(int i=(int)n;i<int(m);++i)
#define rF(i,a,b) for(int i=a;i>=(int)b;--i)
#define mkp(a,b) make_pair(a,b)
#define Fi first
#define Se second
#define int ll
//#pragma GCC optimize("O3")//,unroll-loops
//#pragma GCC target("popcnt")

using namespace std;

template<typename T> bool remax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool remin(T& a, const T& b) {return b<a?a=b,1:0;}
using ll=long long;
using ull=unsigned long long;
using int128= __int128_t;
using uint128= __uint128_t;
using pii =pair<int,int> ;
const double pi=acos(-1);
const int N=1E6+5;
const ll M=105;
const ll INF_64=0x3f3f3f3f3f3f3f3f;
const int INF_32=0x3f3f3f3f;
const int16_t INF_16=0x3f3f;
const int klog=20;
const int mod=1000000007;//1000000007;//998244353
const double eps=1E-3;
void gen(){
}
int BIT[N]{};
int n,m;
int lowbit(int x){return x&(-x);}
void add(int i, int val) {
    BIT[i] = val;
    for (int j = i; j < n; j |= (j + 1)) {
        remax(BIT[j], val);
    }
}

int ask(int i) {
    int res = 0;
    for (int j = i; j >= 0; j = (j & (j + 1)) - 1) {
        remax(res, BIT[j]);
    }
    return res;
}
int a[N];
int an[N];
vector<array<int,3>> Q[N];
void sol(){
    cin>>n>>m;
    F(i,n) cin>>a[i];
    vector<int> stk;
    vector<pii> seg;
    F(i,n){
        while(stk.size()&&a[stk.back()]<=a[i])
                stk.pop_back();
        if(stk.size())
            seg.pb({stk.back(),i});
        stk.pb(i);
    }
    sort(ALL(seg));
    F(i,m){
        int l,r,k;cin>>l>>r>>k;
        Q[l-1].pb({r-1,k,i});
    }
    int id=seg.size()-1;
    rF(i,n-1,0){
        while(id>=0&&seg[id].Fi>=i){
            add(seg[id].Se,a[seg[id].Fi]+a[seg[id].Se]);
            --id;
        }
        for(auto [r,k,ii]:Q[i])
            an[ii]=(ask(r)<=k)?1:0;
    }
    F(i,m) cout<<an[i]<<"\n";
}

int32_t main(){
    #ifdef LOCAL
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    #endif // LOCAL
    IOS;
    int t=1;
    gen();
    //cin>>t;
    FF(i,1,t+1){
        //cout<<"Case #"<<i<<": ";
        sol();
    }
}

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