oj.uz

Submission #151145

# Submission time Handle Problem Language Result Execution time Memory
151145 2019-09-01T21:11:09 Z theboatman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 959 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);
}

void calc(int v, int tl, int tr, int l, int r, int x, int x1,  vector <int> &used, map <pair <int, int>, int> &cost) {
    if (l > r) {
        return;
    }

    if (tl == l && tr == r) {
        int stn = int(t[v].size()) - 1;

        while(stn > -1 && t[v][stn] >= x) {
            int R = t[v][stn], L = used[R];

            int val = cost[make_pair(L, R)];
            cost[make_pair(L, R)] = max(val, x1);

            stn--;
        }

        return;
    }

    int tm = (tl + tr) / 2;
    calc(v * 2, tl, tm, l, min(r, tm), x, x1, used, cost);
    calc(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r, x, x1, used, cost);
}

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

    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 = 1; i < b.size(); i++) {
        int ind = lower_bound(b.begin(), b.end(), make_pair(b[i].first + 1, -inf)) - b.begin() - 1;
        calc(1, 0, int(b.size()) - 1, 0, ind, b[i].second, cost[make_pair(b[i].first, b[i].second)], used, cost);
    }

    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:132:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < b.size(); i++) {
                    ~~^~~~~~~~~~
sortbooks.cpp:145: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 98 ms 94536 KB Output is correct
3 Incorrect 85 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 98 ms 94536 KB Output is correct
3 Incorrect 85 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 959 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 509 ms 114212 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 98 ms 94536 KB Output is correct
3 Incorrect 85 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 98 ms 94536 KB Output is correct
3 Incorrect 85 ms 94328 KB Output isn't correct
4 Halted 0 ms 0 KB -