Submission #161905

#	Time	Username	Problem	Language	Result	Execution time	Memory
161905		Alexa2001	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1157 ms	103196 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e6 + 5;

int w[Nmax];
vector<int> start[Nmax];
int n, m;
int l[Nmax], r[Nmax], val[Nmax], ans[Nmax];

class SegTree
{
    int a[Nmax];
    int ub(int x) { return (x&(-x)); }

public:
    int query(int x)
    {
        int ans = 0;
        for(; x; x-=ub(x)) ans = max(ans, a[x]);
        return ans;
    }

    void update(int pos, int val)
    {
        for(; pos <= n; pos += ub(pos)) a[pos] = max(a[pos], val);
    }
} aib;

void prepare()
{
    int i, nr = 0;
    int st[Nmax];

    for(i=1; i<=n; ++i)
    {
        while(nr && w[st[nr]] <= w[i]) 
            --nr;

        if(nr) start[st[nr]].push_back(i);
        st[++nr] = i;
    }
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
   
    int i;
    for(i=1; i<=n; ++i) cin >> w[i];

    prepare();

    for(i=1; i<=m; ++i) cin >> l[i] >> r[i] >> val[i];

    vector<int> ord;
    for(i=1; i<=m; ++i) ord.push_back(i);

    sort( ord.begin(), ord.end(), [] (int x, int y) { return (l[x] > l[y]); } );
    
    int id = n;
    for(auto it : ord)
    {
        while(id >= l[it])
        {
            for(auto el : start[id])
                aib.update(el, w[id] + w[el]);
            --id;
        }

        ans[it] = (aib.query(r[it]) <= val[it]);
    }

    for(i=1; i<=m; ++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