oj.uz

Submission #867821

# Submission time Handle Problem Language Result Execution time Memory
867821 2023-10-29T14:15:50 Z 12345678 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1464 ms 84616 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;
int n, m, v[nx], l, r, k, ans[nx];
vector<tuple<int, int, int>> d[nx];
stack<int> st;

struct segtree
{
    int d[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i]+=lz[i];
        if (l==r) return void(lz[i]=0);
        lz[2*i]+=lz[i];
        lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void setval(int l, int r, int i, int idx)
    {
        pushlz(l, r, i);
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=v[idx]);
        int md=(l+r)/2;
        setval(l, md, 2*i, idx);
        setval(md+1, r, 2*i+1, idx);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ul, int ur, int vl)
    {
        if (ur<ul) return;
        pushlz(l, r, i);
        if (r<ul||ur<l) return;
        if (ul<=l&&r<=ur) return lz[i]=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ul, ur, vl);
        update(md+1, r, 2*i+1, ul, ur, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (r<ql||qr<l) return INT_MIN;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>v[i];
    for (int i=1; i<=4*n; i++) s.d[i]=INT_MIN;
    v[n+1]=INT_MAX;
    for (int i=0; i<m; i++) cin>>l>>r>>k, d[l].push_back({r, k, i});
    st.push(n+1);
    for (int i=n; i>=1; i--)
    {
        while (st.size()>1&&v[i]>=v[st.top()])
        {
            int x=st.top();
            st.pop();
            s.setval(1, n, 1, x);
            s.update(1, n, 1, x+1, st.top()-1, -v[x]);
        }
        s.update(1, n, 1, i+1, st.top()-1, v[i]);
        st.push(i);
        for (auto [a, b, c]:d[i]) ans[c]=s.query(1, n, 1, i+1, a)<=b;
    }
    for (int i=0; i<m; i++) cout<<ans[i]<<'\n';
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26972 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 5 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 26972 KB Output is correct
6 Correct 6 ms 26972 KB Output is correct
7 Correct 5 ms 26972 KB Output is correct
8 Correct 6 ms 26972 KB Output is correct
9 Correct 6 ms 27164 KB Output is correct
10 Incorrect 7 ms 27072 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26972 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 5 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 26972 KB Output is correct
6 Correct 6 ms 26972 KB Output is correct
7 Correct 5 ms 26972 KB Output is correct
8 Correct 6 ms 26972 KB Output is correct
9 Correct 6 ms 27164 KB Output is correct
10 Incorrect 7 ms 27072 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1443 ms 80596 KB Output is correct
2 Correct 1408 ms 80824 KB Output is correct
3 Correct 1464 ms 80412 KB Output is correct
4 Correct 1422 ms 80532 KB Output is correct
5 Incorrect 1045 ms 84616 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26972 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 5 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 26972 KB Output is correct
6 Correct 6 ms 26972 KB Output is correct
7 Correct 5 ms 26972 KB Output is correct
8 Correct 6 ms 26972 KB Output is correct
9 Correct 6 ms 27164 KB Output is correct
10 Incorrect 7 ms 27072 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26972 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 5 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 26972 KB Output is correct
6 Correct 6 ms 26972 KB Output is correct
7 Correct 5 ms 26972 KB Output is correct
8 Correct 6 ms 26972 KB Output is correct
9 Correct 6 ms 27164 KB Output is correct
10 Incorrect 7 ms 27072 KB Output isn't correct
11 Halted 0 ms 0 KB -