제출 #1100858

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1100858		raphaelp	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2243 ms	166608 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
class SegTree
{
private:
    vector<int> st;
    int N;
    int l(int x) { return (x << 1); }
    int r(int x) { return (x << 1) + 1; }
    void update(int L, int R, int a, int val, int x)
    {
        if (L > a || R < a)
            return;
        if (L == a && R == a)
        {
            st[x] = val;
        }
        else
        {
            int m = (L + R) / 2;
            update(L, m, a, val, l(x));
            update(m + 1, R, a, val, r(x));
            st[x] = min(st[l(x)], st[r(x)]);
        }
    }
    int RMQ(int L, int R, int a, int b, int x)
    {
        if (L > b || R < a)
            return 2000000001;
        if (L >= a && R <= b)
            return st[x];
        int m = (L + R) / 2;
        return min(RMQ(L, m, a, b, l(x)), RMQ(m + 1, R, a, b, r(x)));
    }

public:
    SegTree(int x)
    {
        N = pow(2, ceil(log2(x)));
        st.assign(2 * N, 2000000001);
    }
    void update(int x, int val) { update(0, N - 1, x, val, 1); }
    int RMQ(int a, int b) { return RMQ(0, N - 1, a, b, 1); }
};
int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> Tab(N);
    for (int i = 0; i < N; i++)
        cin >> Tab[i];
    vector<vector<int>> Qs(M, vector<int>(4));
    for (int i = 0; i < M; i++)
    {
        cin >> Qs[i][1] >> Qs[i][2] >> Qs[i][0];
        Qs[i][1]--, Qs[i][2]--;
        Qs[i][3] = i;
    }
    sort(Qs.begin(), Qs.end());
    set<pair<int, int>> S;
    vector<int> rig(N, N);
    for (int i = N - 1; i >= 0; i--)
    {
        auto pos = S.lower_bound({Tab[i], 0});
        if (pos != S.end())
            rig[i] = pos->second;
        S.insert({Tab[i], i});
        while (S.lower_bound({Tab[i], i}) != S.begin())
        {
            S.erase(S.begin());
        }
    }
    vector<vector<int>> events;
    for (int i = 0; i < N; i++)
    {
        int x = i + 1;
        while (x < N && Tab[x] < Tab[i])
        {
            events.push_back({Tab[x] + Tab[i], i, x});
            x = rig[x];
        }
    }
    sort(events.begin(), events.end());
    SegTree ST(N);
    vector<int> ans(M);
    int buff = events.size() - 1;
    for (int i = M - 1; i >= 0; i--)
    {
        while (buff >= 0 && events[buff][0] > Qs[i][0])
        {
            ST.update(events[buff][1], events[buff][2]);
            buff--;
        }
        if (ST.RMQ(Qs[i][1], Qs[i][2]) > Qs[i][2])
            ans[Qs[i][3]] = 1;
    }
    for (int i = 0; i < M; i++)
    {
        cout << ans[i] << '\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