Submission #894535

#	Time	Username	Problem	Language	Result	Execution time	Memory
894535		Andrey	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	982 ms	88320 KiB

sortbooks

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

vector<int> seg(4000001);
vector<int> wow(4000001);

int calc(int l, int r, int ql, int qr, int x) {
    if(l == ql && r == qr) {
        return seg[x];
    }
    int m = (l+r)/2,ans = 0;
    if(qr <= m) {
        ans = calc(l,m,ql,qr,x*2+1);
    }
    else if(ql > m) {
        ans = calc(m+1,r,ql,qr,x*2+2);
    }
    else {
        ans = calc(l,m,ql,m,x*2+1);
        ans = max(ans,calc(m+1,r,m+1,qr,x*2+2));
    }
    return max(ans,wow[x]);
}

void upd(int l, int r, int ql, int qr, int x, int a) {
    if(l == ql && r == qr) {
        wow[x] = max(wow[x],a);
        seg[x] = max(seg[x],a);
        return;
    }
    int m = (l+r)/2;
    if(qr <= m) {
        upd(l,m,ql,qr,x*2+1,a);
    }
    else if(ql > m) {
        upd(m+1,r,ql,qr,x*2+2,a);
    }
    else {
        upd(l,m,ql,m,x*2+1,a);
        upd(m+1,r,m+1,qr,x*2+2,a);
    }
    seg[x] = max(seg[x*2+1],seg[x*2+2]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,q,a,b,c,y = 0;
    cin >> n >> q;
    vector<pair<pair<int,int>,int>> bruh(0);
    vector<int> haha(n+1,1e9+10);
    vector<int> wow(q);
    vector<int> ans(q);
    for(int i = 1; i <= n; i++) {
        cin >> haha[i];
    }
    for(int i = 0; i < q; i++) {
        cin >> a >> b >> wow[i];
        bruh.push_back({{b,a},i});
    }
    sort(bruh.begin(),bruh.end());
    vector<pair<int,int>> idk(1,{haha[0],0});
    for(int i = 1; i <= n; i++) {
        while(haha[i] >= idk[idk.size()-1].first) {
            idk.pop_back();
        }
        if(idk.size() > 1) {
            upd(1,n,idk[idk.size()-2].second+1,idk[idk.size()-1].second,0,haha[i]+idk[idk.size()-1].first);
        }
        idk.push_back({haha[i],i});
        while(y < q && bruh[y].first.first == i) {
            int r = bruh[y].first.first,l = bruh[y].first.second;
            ans[bruh[y].second] = calc(1,n,l,r,0);
            y++;
        }
    }
    for(int i = 0; i < q; i++) {
        cout << (ans[i] <= wow[i]) << "\n";
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:50:17: warning: unused variable 'c' [-Wunused-variable]
   50 |     int n,q,a,b,c,y = 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