Submission #1279236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279236		herominhsteve	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	814 ms	72896 KiB

sortbooks

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "Library"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const long long INF = (long long) 1e17 + 15092007;

struct SegmentTree{
    int n;
    vector<long long> st;

    SegmentTree(int N=0){
        n = N;
        if (n>0){
            st.assign(4 * n + 4, -INF);
        }
    }

    void update(int node,int l,int r,int pos,long long val){
        if (l > r) return;
        if (l==r){
            maximize(st[node],val);
            return;
        }
        int mid = (l+r)>>1;
        if (pos <= mid) update(2*node,l,mid,pos,val);
        else update(2*node+1,mid+1,r,pos,val);
        st[node] = max(st[2*node],st[2*node+1]);
    }

    void update(int pos,long long val){
        update(1,1,n,pos,val);
    }

    long long getMax(int node,int l,int r,int wanted_l,int wanted_r){
        if (wanted_r < l or r < wanted_l) return -INF;
        if (wanted_l <= l and r <= wanted_r) return st[node];
        int mid = (l+r)>>1;
        return max(getMax(2*node,l,mid,wanted_l,wanted_r),
                    getMax(2*node+1,mid+1,r,wanted_l,wanted_r));
    }

    long long getMax(int l,int r){
        return getMax(1,1,n,l,r);
    }
};  

struct Query{
    int l,r,K,ID;
    Query(int L,int R,int K,int ID):l(L),r(R),K(K),ID(ID) {}
    bool operator < (const Query &other) const{
        return (r < other.r or (r==other.r and l < other.l));
    }
};

int n,q;
vector<long long> a;
vector<Query> query;

void init(){
	cin>>n>>q;
    a.assign(n+1,0);
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=0;i<q;i++){
        int l,r,k;
        cin>>l>>r>>k;
        query.emplace_back(l,r,k,i);
    }
}

void sol(){
	stack<int> st;
    vector<int> ngel(n+1,0);
    vector<long long> inverVal(n+1,0);

    for (int i=1;i<=n;i++){
        while (!st.empty() and a[st.top()] <= a[i]) st.pop();
        ngel[i] = (st.empty() ? 0 : st.top());
        if (!st.empty()) inverVal[i] = a[i] + a[ngel[i]];
        st.push(i);
    }

    sort(allof(query));

    // * ST on L and query on R
    SegmentTree ST(n);

    vector<int> res(q,0);
    int ptr = 0;    
    for (int r = 1; r <= n; r++){
        if (ngel[r]) ST.update(ngel[r],inverVal[r]);
        while (ptr < q and query[ptr].r == r){
            int L = query[ptr].l;
            int R = query[ptr].r;
            int K = query[ptr].K;
            int ID = query[ptr].ID;
            long long maxRange = ST.getMax(L,R);
            if (maxRange == -INF) res[ID] = 1;
            else res[ID] = (maxRange <= K);
            ptr++;
        }
    }
    for (int x : res) cout<<x<<el;
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

sortbooks.cpp: In function 'void setup()':
sortbooks.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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