oj.uz

Submission #1087801

# Submission time Handle Problem Language Result Execution time Memory
1087801 2024-09-13T08:53:51 Z PanosPask Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 1100 ms 82996 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

typedef pair<int, int> pi;

const int INF = 1e9 + 1;

struct SegTree {
    int size;
    vector<int> tree;

    void init(int N) {
        size = 1;
        while (size < N) {
            size *= 2;
        }

        tree.assign(2 * size, -INF);
    }

    void set(int i, int v, int x, int lx, int rx) {
        if (lx == rx - 1) {
            tree[x] = v;
            return;
        }

        int mid = (lx + rx) / 2;
        if (i < mid) {
            set(i, v, 2 * x + 1, lx, mid);
        }
        else {
            set(i, v, 2 * x + 2, mid, rx);
        }

        tree[x] = max(tree[2 * x + 1], tree[2 * x + 2]);
    }
    void set(int i, int v) {
        set(i, v, 0, 0, size);
    }

    int calc(int l, int r, int x, int lx, int rx) {
        if (lx >= r || l >= rx) {
            return -INF;
        }
        else if (l <= lx && rx <= r) {
            return tree[x];
        }

        int mid = (lx + rx) / 2;

        return max(calc(l, r, 2 * x + 1, lx, mid), calc(l, r, 2 * x + 2, mid, rx));
    }
    int calc(int l, int r) {
        return calc(l, r, 0, 0, size);
    }
};

struct Query {
    int l, r, k;

    int id;
};

bool querysort(Query a, Query b) 
{
    return a.l > b.l;
}

int N, M;
vector<int> w;
vector<Query> queries;
vector<int> ans;
SegTree st;
SegTree vals;

int invcomp(int a, int b)
{
    return a > b;
}

// Get last place in local maximum array that is BEFORE r
int getlast(int r, vector<int>& s)
{
    int pos = upper_bound(s.begin(), s.end(), r, invcomp) - s.begin();

    return s[pos];
}

int main(void)
{
    scanf("%d %d", &N, &M);

    w.resize(N);
    st.init(N + 1);
    vals.init(N + 1);
    queries.resize(M);
    ans.resize(M);

    for (int i = 0; i < N; i++) {
        scanf("%d", &w[i]);
    }
    w.pb(INF);

    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &queries[i].l, &queries[i].r, &queries[i].k);
        queries[i].l--;
        queries[i].id = i;
    }
    sort(queries.begin(), queries.end(), querysort);

    vector<int> s;
    s.pb(N);
    int p = 0;
    for (int i = N - 1; i >= 0; i--) {
        while (w[s.back()] <= w[i]) {
            vals.set(s.back(), -INF);
            s.pop_back();
        }
        st.set(i, w[i]);

        int res = st.calc(i + 1, s.back());
        if (res >= 0) {
            res += w[i];
        }
        vals.set(i, res);
        s.pb(i);

        while (p < M && queries[p].l == i) {
            Query cur = queries[p];

            int pos = getlast(cur.r, s);
            int res = vals.calc(cur.l, pos);
            if (pos + 1 != cur.r) {
                res = max(res, st.calc(pos + 1, cur.r) + w[pos]);
            }

            ans[cur.id] = res <= cur.k;

            p++;
        }
    }

    for (int i = 0; i < M; i++) {
        printf("%d\n", ans[i]);
    }

    return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%d %d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         scanf("%d", &w[i]);
      |         ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         scanf("%d %d %d", &queries[i].l, &queries[i].r, &queries[i].k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1094 ms 44116 KB Output is correct
2 Correct 1073 ms 75192 KB Output is correct
3 Correct 1100 ms 74852 KB Output is correct
4 Correct 1089 ms 75020 KB Output is correct
5 Incorrect 1064 ms 82996 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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