oj.uz

Submission #581402

# Submission time Handle Problem Language Result Execution time Memory
581402 2022-06-22T15:17:42 Z islingr Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 19604 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using ld = long double;

#define rep(i, a, b) for (auto i{a}; i < (b); ++i)
#define per(i, a, b) for (auto i{b}; i-- > (a);)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) static_cast<int>((x).size())

template <class T>
bool uin(T& a, const T& b) {
    return a > b ? a = b, true : false;
}
template <class T>
bool uax(T& a, const T& b) {
    return a < b ? a = b, true : false;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct segment_tree {
    static constexpr int inf = 1e9;
    int n;
    vector<int> t;
    segment_tree() {}
    segment_tree(int n) : n{n}, t(2 * n, -inf) {}
    int query(int l, int r) {
        int res = -inf;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, t[l++]);
            if (r & 1) res = max(res, t[--r]);
        }
        return res;
    }
    void update(int p, int x) {
        for (t[p += n] = x; p >>= 1;) t[p] = max(t[p << 1], t[p << 1 | 1]);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        --l;

        vector<pair<int, int>> v;
        rep(i, l, r) v.emplace_back(a[i], i - l);
        sort(all(v));

        segment_tree t(r - l);
        bool poss = true;
        rep(i, 0, r - l) {
            auto [p, y] = v[i];
            auto q = t.query(y, r - l);
            poss &= p + q <= k;
            if (!poss) break;
            t.update(y, p);
        }
        cout << poss << '\n';
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 368 KB Output is correct
7 Correct 9 ms 340 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 6 ms 352 KB Output is correct
10 Correct 13 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 368 KB Output is correct
7 Correct 9 ms 340 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 6 ms 352 KB Output is correct
10 Correct 13 ms 348 KB Output is correct
11 Correct 163 ms 376 KB Output is correct
12 Correct 559 ms 572 KB Output is correct
13 Correct 651 ms 608 KB Output is correct
14 Correct 1072 ms 492 KB Output is correct
15 Correct 1077 ms 608 KB Output is correct
16 Correct 1783 ms 720 KB Output is correct
17 Correct 1575 ms 648 KB Output is correct
18 Correct 1459 ms 676 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3072 ms 19604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3082 ms 2540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 368 KB Output is correct
7 Correct 9 ms 340 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 6 ms 352 KB Output is correct
10 Correct 13 ms 348 KB Output is correct
11 Correct 163 ms 376 KB Output is correct
12 Correct 559 ms 572 KB Output is correct
13 Correct 651 ms 608 KB Output is correct
14 Correct 1072 ms 492 KB Output is correct
15 Correct 1077 ms 608 KB Output is correct
16 Correct 1783 ms 720 KB Output is correct
17 Correct 1575 ms 648 KB Output is correct
18 Correct 1459 ms 676 KB Output is correct
19 Execution timed out 3061 ms 6968 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 368 KB Output is correct
7 Correct 9 ms 340 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 6 ms 352 KB Output is correct
10 Correct 13 ms 348 KB Output is correct
11 Correct 163 ms 376 KB Output is correct
12 Correct 559 ms 572 KB Output is correct
13 Correct 651 ms 608 KB Output is correct
14 Correct 1072 ms 492 KB Output is correct
15 Correct 1077 ms 608 KB Output is correct
16 Correct 1783 ms 720 KB Output is correct
17 Correct 1575 ms 648 KB Output is correct
18 Correct 1459 ms 676 KB Output is correct
19 Execution timed out 3072 ms 19604 KB Time limit exceeded
20 Halted 0 ms 0 KB -