Submission #502780

#	Time	Username	Problem	Language	Result	Execution time	Memory
502780		blue	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1266 ms	104916 KiB

sortbooks

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;

const ll INF = 1'000'000'000'000LL;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    vll w(1+N, 0);
    for(int i = 1; i <= N; i++) cin >> w[i];

    vi p(1+N);

    w[0] = INF;
    vector<int> st{0};

    for(int i = 1; i <= N; i++)
    {
        while(w[st.back()] <= w[i]) st.pop_back(); //wrong?
        p[i] = st.back();
        st.push_back(i);
    }

    vi l(1+M), r(1+M), k(1+M);
    vi rq[1+N];
    for(int q = 1; q <= M; q++)
    {
        cin >> l[q] >> r[q] >> k[q];
        rq[r[q]].push_back(q);
    }

    const int sn = (1<<20);

    vll mx(int(sn<<1), 0);

    int ans[1+M];

    for(int i = 1; i <= N; i++)
    {
        ll val = w[i] + w[p[i]];
        mx[ sn + p[i] ] = max(mx[ sn + p[i] ], val);

        for(int j = (sn + p[i]) >> 1; j >= 1; j >>= 1)
            mx[j] = max(mx[2*j], mx[2*j+1]);


        for(int q: rq[i])
        {
            int x = sn + l[q];
            int y = sn + i + 1;

            ll res = 0;

            while(x < y)
            {
                if(x % 2 == 1)
                {
                    res = max(res, mx[x]);
                    x++;
                }
                if(y % 2 == 1)
                {
                    y--;
                    res = max(res, mx[y]);
                }
                x >>= 1;
                y >>= 1;
            }

            ans[q] = (res <= k[q]);
        }
    }

    for(int q = 1; q <= M; q++) cout << ans[q] << '\n';
}

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