oj.uz

Submission #151139

# Submission time Handle Problem Language Result Execution time Memory
151139 2019-09-01T20:53:47 Z theboatman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1170 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 <pair <int, int> > b;
    map <pair <int, int>, int> cost;

    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;

            b.push_back(make_pair(l, r));
            cost[make_pair(l, r)] = a[l] + a[r];

            used[r] = l;
        }

        st.push_back(i);
    }

    sort(b.begin(), b.end());

    while(st.size()) {
        st.pop_back();
    }

    for(int i = 0; i < b.size(); i++) {
        while(st.size() && !(b[st.back()].first <= b[i].first && b[i].second <= b[st.back()].second)) {
            int val = cost[make_pair(b[st.back()].first, b[st.back()].second)];
            st.pop_back();

            if (st.size()) {
                int val1 = cost[make_pair(b[st.back()].first, b[st.back()].second)];
                cost[make_pair(b[st.back()].first, b[st.back()].second)] = max(val, val1);
            }
        }

        st.push_back(i);
    }

    if (!b.size()) {
        for(int i = 0; i < m; i++) {
            int l, r, k;
            cin >> l >> r >> k;

            cout << "1\n";
        }
        return 0;
    }

    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()) {
            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

5 2
1 2 3 5 4

*/

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:99:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < b.size(); i++) {
                    ~~^~~~~~~~~~
sortbooks.cpp:133:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (ind != b.size()) {
             ~~~~^~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 94200 KB Output is correct
2 Correct 88 ms 94364 KB Output is correct
3 Incorrect 86 ms 94328 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 94200 KB Output is correct
2 Correct 88 ms 94364 KB Output is correct
3 Incorrect 86 ms 94328 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1170 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 430 ms 114432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 94200 KB Output is correct
2 Correct 88 ms 94364 KB Output is correct
3 Incorrect 86 ms 94328 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 94200 KB Output is correct
2 Correct 88 ms 94364 KB Output is correct
3 Incorrect 86 ms 94328 KB Output isn't correct
4 Halted 0 ms 0 KB -