Submission #334404

#	Time	Username	Problem	Language	Result	Execution time	Memory
334404		limabeans	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1867 ms	92284 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl






const int inf = 2e9;
const int maxn = 1e6 + 5;


struct query {
    int l,r,k;
    void read() {
	cin>>l>>r>>k;
    }
};

int n,q;
int t[maxn*4];



void upd(int v, int tl, int tr, int i, int val) {
    if (tl==tr) {
	t[v]=max(t[v],val);
    } else {
	int tm=(tl+tr)/2;
	if (i<=tm) {
	    upd(2*v,tl,tm,i,val);
	} else {
	    upd(2*v+1,tm+1,tr,i,val);
	}
	t[v]=max(t[2*v],t[2*v+1]);
    }
}

int qry(int v, int tl, int tr, int l, int r) {
    if (l>tr || r<tl) return -inf;
    if (l<=tl && tr<=r) return t[v];
    int tm=(tl+tr)/2;
    return max(qry(2*v,tl,tm,l,r),qry(2*v+1,tm+1,tr,l,r));
}

int a[maxn];

query Q[maxn];
vector<int> ev[maxn];
int ans[maxn];


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n>>q;

    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }
    for (int i=1; i<=q; i++) {
	Q[i].read();
	ev[Q[i].r].push_back(i);
    }

    stack<int> stk;
    vector<pair<int,int>> w;
    for (int i=1; i<=n; i++) {
	while (!stk.empty() && a[stk.top()]<=a[i]) stk.pop();
	if (!stk.empty()) w.push_back({i,stk.top()});
	stk.push(i);
    }

    sort(w.begin(),w.end());
    int j=0;
    for (int i=1; i<=n; i++) {
	while (j<(int)w.size() && w[j].first<=i) {
	    upd(1,1,n,w[j].second, a[w[j].first]+a[w[j].second]);
	    ++j;
	}

	for (int qi: ev[i]) {
	    if (qry(1,1,n,Q[qi].l,Q[qi].r)<=Q[qi].k) ans[qi]=1;
	}
    }
    


    for (int i=1; i<=q; i++) {
	cout<<ans[i]<<"\n";
    }
    
    
    return 0;
}

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