Submission #1279200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279200		herominhsteve	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	575 ms	65892 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);
	}
}

using ll = long long;
const ll NEG = -(1LL<<60);

struct Query {
    int l, r;
    ll k;
    int id;
};

int n, q;
vector<ll> a;
vector<int> prevGreater;
vector<ll> pairVal; 

struct SegTree {
    int base; 
    vector<ll> t;
    SegTree(): base(0) {}
    void init(int N){
        base = 1;
        while(base < N) base <<= 1;
        t.assign(2*base, NEG);
    }
    void point_update_max(int pos, ll val){
        int p = pos - 1 + base;
        t[p] = max(t[p], val);
        p >>= 1;
        while(p){
            t[p] = max(t[p<<1], t[p<<1|1]);
            p >>= 1;
        }
    }
    ll range_max(int l, int r){
        if (l > r) return NEG;
        int L = l - 1 + base, R = r - 1 + base;
        ll res = NEG;
        while(L <= R){
            if (L & 1) { res = max(res, t[L]); ++L; }
            if (!(R & 1)) { res = max(res, t[R]); --R; }
            L >>= 1; R >>= 1;
        }
        return res;
    }
} seg;

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

    prevGreater.assign(n+1, 0);
    pairVal.assign(n+1, NEG);

    vector<int> st;
    st.reserve(n);
    for(int i=1;i<=n;i++){
        while(!st.empty() && a[st.back()] <= a[i]) st.pop_back();
        if (!st.empty()) prevGreater[i] = st.back();
        else prevGreater[i] = 0;
        st.push_back(i);
        if (prevGreater[i] > 0) pairVal[i] = a[i] + a[prevGreater[i]];
    }
}

void sol(){
    vector<Query> qs;
    qs.reserve(q);
    for(int i=0;i<q;i++){
        int l,r; ll k; cin >> l >> r >> k;
        qs.push_back({l,r,k,i});
    }
    sort(qs.begin(), qs.end(), [](const Query &A, const Query &B){
        if (A.r != B.r) return A.r < B.r;
        return A.l < B.l;
    });

    seg.init(n);

    vector<int> ans(q, 0);
    int ptr = 0;
    for(int r=1; r<=n; ++r){
        if (prevGreater[r] > 0){
            seg.point_update_max(prevGreater[r], pairVal[r]);
        }
        while(ptr < (int)qs.size() && qs[ptr].r == r){
            int L = qs[ptr].l;
            int R = qs[ptr].r;
            ll k = qs[ptr].k;
            int id = qs[ptr].id;
            ll mx = seg.range_max(L, R);
            if (mx == NEG) ans[id] = 1; 
            else ans[id] = (mx <= k) ? 1 : 0;
            ++ptr;
        }
    }
    for(int i=0;i<q;i++){
        cout << ans[i] << el;
    }
}

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

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