oj.uz

Submission #147814

# Submission time Handle Problem Language Result Execution time Memory
147814 2019-08-30T18:21:39 Z theboatman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 568 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, k;
};

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

vector <int> t[N * 2 * 4];
void build(int v, int tl, int tr, vector <pair <int, int> > &a) {
    if (tl > tr) {
        return;
    }

    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 != -1) {
            return t[v][ind];
        }
        else {
            return -1;
        }
    }

    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(tm + 1, l), 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(auto &i : a) {
        cin >> i;
    }

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

        if (st.size()) {
            c.push_back(make_struct(st.back(), i, a[i] + a[st.back()]));
        }

        st.push_back(i);
    }

    map <pair <int, int>, int> mp;
    vector <pair <int, int> > kek;
    for(int i = 0; i < c.size(); i++) {
        int l = c[i].l, r = c[i].r, res = c[i].x;
        vector <int> s;
        while(i < c.size() && c[i].l <= l && r <= c[i].r) {
            res = max(res, c[i].x);

            s.push_back(i);

            l = c[i].l;
            r = c[i].r;
            i++;
        }
        i--;

        reverse(s.begin(), s.end());

        res = -inf;
        int stn = s.size() - 1;
        while(stn > -1) {
            res = max(res, c[s[stn]].x);
            int L = c[s[stn]].l;
            int R = c[s[stn]].r;

            mp[make_pair(L, R)] = res;
            kek.push_back(make_pair(L, R));

            stn--;
        }
    }


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

    int _n = kek.size();
    build(1, 0, _n - 1, kek);

    vector <osu> b(m);
    for(auto &i : b) {
        cin >> i.l >> i.r >> i.k;
        i.l--, i.r--;

        pair <int, int> p = make_pair(i.l, i.r);
        int ind = lower_bound(kek.begin(), kek.end(), p) - kek.begin();

        int R = get(1, 0, _n - 1, ind, _n - 1, i.r);

        int res = 0;
        if (R != -1) {
            res = mp[make_pair(kek[ind].first, R)];
        }

        cout << (res <= i.k) << "\n";
    }

    return 0;
}

/*
*/

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:95:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < c.size(); i++) {
                    ~~^~~~~~~~~~
sortbooks.cpp:98:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i < c.size() && c[i].l <= l && r <= c[i].r) {
               ~~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 188152 KB Output is correct
2 Correct 171 ms 188200 KB Output is correct
3 Incorrect 170 ms 188308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 188152 KB Output is correct
2 Correct 171 ms 188200 KB Output is correct
3 Incorrect 170 ms 188308 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 544 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 568 ms 216268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 188152 KB Output is correct
2 Correct 171 ms 188200 KB Output is correct
3 Incorrect 170 ms 188308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 188152 KB Output is correct
2 Correct 171 ms 188200 KB Output is correct
3 Incorrect 170 ms 188308 KB Output isn't correct
4 Halted 0 ms 0 KB -