oj.uz

Submission #498607

# Submission time Handle Problem Language Result Execution time Memory
498607 2021-12-25T18:40:01 Z RedBoy Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++11
0 / 100
 1122 ms 63768 KB 
#include <iostream>
#include <stack>
#include <vector>
#include <bitset>

using namespace std;

const int N = 1e6 + 5;
const int INF = 2e9;

struct query{
    int ind, l, k;
};

int n, m;
int l[N], v[N], st[4 * N];
stack<int> s;
vector<query> q[N];
bitset<N> bit;

void update(int node, int l, int r, int pos, int val)
{
    if(l == r)
    {
        //cout << "UPDATE: " << node << ' ' << val << '\n';
        st[node] = max(st[node], val);
        return;
    }

    int lNode = node * 2, rNode = node * 2 + 1;
    int mid = (l + r) / 2;

    if(pos <= mid)
        update(lNode, l, mid, pos, val);
    else
        update(rNode, mid + 1, r, pos, val);

    st[node] = max(st[lNode], st[rNode]);
}

int get(int node, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr)
        return st[node];

    int lNode = node * 2, rNode = node * 2 + 1, mid = (l + r) / 2, ans = -INF;
    if(ql <= mid)
        ans = max(ans, get(lNode, l, mid, ql, qr));
    else
        ans = max(ans, get(rNode, mid + 1, r, ql, qr));

    return ans;
}

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

    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> v[i];
    for(int i = 1; i <= m; i++)
    {
        int l, r, k;
        cin >> l >> r >> k;
        q[r].push_back({i, l, k});
    }

    for(int i = 1; i <= n; i++)
    {
        l[i] = i;
        while(!s.empty() && v[i] >= v[s.top()])
        {
            l[i] = l[s.top()];
            s.pop();
        }
        s.push(i);
    }

    for(int i = 1; i <= n; i++)
    {
        //cout << "ARRAY: " << i << ' ' << l[i] - 1 << '\n';
        if(l[i] > 1)
            update(1, 1, n, l[i] - 1, v[i] + v[l[i] - 1]);
        for(auto it: q[i])
        {
            //cout << it.ind << ": " << it.l << ' ' << i << ' ' << it.k << '\n';
            //cout << get(1, 1, n, it.l, i) << "\n\n";
            bit[it.ind] = (it.k >= get(1, 1, n, it.l, i));
        }
    }

    for(int i = 1; i <= m; i++)
        cout << bit[i] << '\n';
    cout << '\n';

    return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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