oj.uz

Submission #992778

# Submission time Handle Problem Language Result Execution time Memory
992778 2024-06-05T07:19:36 Z NValchanov Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 686 ms 34996 KB 
#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;

struct SegmentTree
{
    int n;
    int tree[4 * MAXN];
    int w[MAXN];

    void init(int _n, int _w[])
    {
        n = _n;
        for(int i = 1; i <= n; i++)
        {
            w[i] = _w[i];
        }
    }

    void update(int left, int right, int idx, int pos, int val)
    {
        if(pos < left || right < pos)
            return;

        if(left == right)
        {
            tree[idx] = max(tree[idx], val + w[left]);
            return;
        }

        int mid = left + (right - left) / 2;

        update(left, mid, 2 * idx, pos, val);
        update(mid + 1, right, 2 * idx + 1, pos, val);
    } 

    int query(int left, int right, int idx, int qleft, int qright)
    {
        if(qright < left || right < qleft)
            return 0;

        if(qleft <= left && right <= qright)
            return tree[idx];

        int mid = left + (right - left) / 2;

        int Lnode = query(left, mid, 2 * idx, qleft, qright);
        int Rnode = query(mid + 1, right, 2 * idx + 1, qleft, qright);

        return max(Lnode, Rnode);
    }

    void update(int pos, int val)
    {
        update(1, n, 1, pos, val);
    }

    int query(int left, int right)
    {
        return query(1, n, 1, left, right);
    }
};

struct qry
{
    int left, right;
    int k;
    int idx;

    qry()
    {
        left = right = 1;
        k = 0;
        idx = 1;
    }

    qry(int _left, int _right, int _k, int _idx)
    {
        left = _left;
        right = _right;
        k = _k;
        idx = _idx;
    }

    friend bool operator<(const qry&q1, const qry&q2)
    {
        if(q1.left != q2.left)
            return q1.left < q2.left;
        return q1.right < q2.right;
    }
};

int n, q;
int w[MAXN];
bool ans[MAXN];
vector < qry > queries;
SegmentTree t;

void read()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i];
    }
    for(int i = 1; i <= q; i++)
    {
        int left, right, k;
        cin >> left >> right >> k;
        qry cur = qry(left, right, k, i);

        queries.push_back(cur);
    }
}

void solve()
{
    t.init(n, w);
    sort(queries.begin(), queries.end());

    stack < int > st;
    int ptr = 1;

    for(qry c : queries)
    {
        int left = c.left;
        int right = c.right;
        int k = c.k;
        int idx =  c.idx;

        while(ptr <= right)
        {
            while(!st.empty() && w[st.top()] <= w[ptr])
                st.pop();

            if(!st.empty())
                t.update(st.top(), w[ptr]);

            st.push(ptr);

            ptr++;
        }

        int cur = t.query(left, right);

        ans[idx] = (cur <= k);
    }
}

void print()
{
    for(int i = 1; i <= q; i++)
    {
        cout << ans[i] << endl;
    }
}

int main()
{
    #ifdef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    read();
    solve();
    print();

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 686 ms 34996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 9184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -