oj.uz

Submission #151135

# Submission time Handle Problem Language Result Execution time Memory
151135 2019-09-01T20:30:35 Z theboatman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 873 ms 262148 KB 
#include <bits/stdc++.h>

#define y1 theboatman
#define make_struct(args...) {args}

using namespace std;

typedef long long ll;

const long long INF = 1e18 + 10;
const int inf = 1e9 + 10;
const int N = 1e6 + 10;

struct osu {
    int l, r, x;
};

vector <int> t[N * 4];
void build(int v, int tl, int tr, vector <pair <int, int> > &a) {
    if (tl == tr) {
        t[v].push_back(a[tl].second);
    }
    else {
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm, a);
        build(v * 2 + 1, tm + 1, tr, a);

        t[v] = t[v * 2];
        for(auto i : t[v * 2 + 1]) {
            t[v].push_back(i);
        }

        sort(t[v].begin(), t[v].end());
    }
}

int get(int v, int tl, int tr, int l, int r, int x) {
    if (l > r) {
        return -1;
    }

    if (tl == l && tr == r) {
        int ind = lower_bound(t[v].begin(), t[v].end(), x + 1) - t[v].begin() - 1;
        if (ind < 0) {
            return -1;
        }
        else {
            return t[v][ind];
        }
    }

    int tm = (tl + tr) / 2;
    int ql = get(v * 2, tl, tm, l, min(r, tm), x);
    int qr = get(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, x);

    return max(ql, qr);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    vector <int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector <int> st;
    vector <int> used(n, -1);
    vector <multiset <int> > add(n + 1), del(n);

    for(int i = 0; i < n; i++) {
        while(st.size() && a[st.back()] < a[i]) {
            st.pop_back();
        }

        if (st.size()) {
            int l = st.back(), r = i;

            add[0].insert(a[l] + a[r]);
            add[r + 1].insert(a[l] + a[r]);

            del[l].insert(a[l] + a[r]);

            used[r] = l;
        }

        st.push_back(i);
    }

    multiset <int> now;
    vector <pair <int, int> > b;
    map <pair <int, int>, int> cost;

    now.insert(0);
    for(int i = 0; i < n; i++) {
        for(auto x : add[i]) {
            now.insert(x);
        }

        for(auto x : del[i]) {
            now.erase(now.find(x));
        }

        if (used[i] != -1) {
            int r = i, l = used[i];

            cost[make_pair(l, r)] = *--now.end();
            b.push_back(make_pair(l, r));
        }
    }


    build(1, 0, int(b.size()) - 1, b);

    for(int i = 0; i < m; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        l--, r--;

        int ind = lower_bound(b.begin(), b.end(), make_pair(l, -inf)) - b.begin();

        int x = 0;
        if (ind != b.size()) {
            int r = get(1, 0, int(b.size()) - 1, ind, int(b.size()) - 1, r);

            if (r != -1) {
                x = cost[make_pair(used[r], r)];
            }
        }

        cout << (x <= k) << "\n";
    }
    return 0;
}
/*
5 2
3 5 1 8 2
1 3 6
2 5 3
*/

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:127:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (ind != b.size()) {
             ~~~~^~~~~~~~~~~
sortbooks.cpp:128:24: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
             int r = get(1, 0, int(b.size()) - 1, ind, int(b.size()) - 1, r);
                     ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 873 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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