Submission #172330

#	Time	Username	Problem	Language	Result	Execution time	Memory
172330		muradeyn	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	737 ms	80244 KiB

sortbooks

/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#define F first
#define S second

using namespace std;

const int maxx = 1000005;

int n , m;
int we[maxx] , ans[maxx] , inv[maxx] , tree[maxx];

vector< int >st;
vector< pair< pair<int,int> , pair<int,int> > >v;

void update(int v,int l,int r,int in,int val) {
    if (l == r) {
        tree[v] = max(tree[v] , val);
        return;
    }
    int mid = (l + r) >> 1;
    if (in <= mid)update(v << 1,l,mid,in,val);
    else update(v << 1 | 1,mid + 1,r,in,val);
    tree[v] = max(tree[v << 1] , tree[v << 1 | 1]);
}

int get(int v,int l,int r,int le,int ri) {
    if (l > ri || r < le)return 0;
    if (l >= le && r <= ri)return tree[v];
    int mid = (l + r) >> 1;
    return max(get(v << 1,l,mid,le,ri) , get(v << 1 | 1,mid + 1,r,le,ri));
}

int main() {
	FAST_READ;
	cin>>n>>m;
	for (int i = 1;i<=n;i++)cin>>we[i];
	for (int i = 1;i<=m;i++) {
        int l, r, k;
        cin>>l>>r>>k;
        v.push_back({{l , r} , {k , i}});
	}
	sort(v.begin(),v.end());
    for (int i = 1;i <= n;i++) {
        while (!st.empty() && we[st.back()] <= we[i])st.pop_back();
        if (st.empty())inv[i] = -1;
        else inv[i] = st.back();
        st.push_back(i);
    }
    for (int i = n;i >= 1;i--) {
        if (inv[i] != -1)update(1 , 1 , n , inv[i] , we[i] + we[inv[i]]);
        //cout<<i<<" "<<inv[i]<<endl;
        while (!v.empty() && v.back().F.F == i) {
            //cout<<v.back().F.F<<" "<<v.back().F.S<<endl;
            ans[v.back().S.S] = (get(1 , 1 , n , v.back().F.F , v.back().F.S) <= v.back().S.F);
            v.pop_back();
        }
    }
    for (int i = 1;i<=m;i++)cout<<ans[i]<<endl;
}

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