oj.uz

Submission #905706

# Submission time Handle Problem Language Result Execution time Memory
905706 2024-01-13T04:20:52 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1275 ms 96460 KB 
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #include <x86intrin.h>

#include <bits/stdc++.h>
#include <chrono>
#include <random>

// @author: Vlapos

namespace operators
{
    template <typename T1, typename T2>
    std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
    {
        in >> x.first >> x.second;
        return in;
    }

    template <typename T1, typename T2>
    std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
    {
        out << x.first << " " << x.second;
        return out;
    }

    template <typename T1>
    std::istream &operator>>(std::istream &in, std::vector<T1> &x)
    {
        for (auto &i : x)
            in >> i;
        return in;
    }

    template <typename T1>
    std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
    {
        for (auto &i : x)
            out << i << " ";
        return out;
    }

    template <typename T1>
    std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
    {
        for (auto &i : x)
            out << i << " ";
        return out;
    }
}

// name spaces
using namespace std;
using namespace operators;
// end of name spaces

// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines

// usefull stuff

void boost()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

inline int getbit(int &x, int &bt) { return (x >> bt) & 1; }

const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1};

const ll INF = (1e18) + 500;
const int BIG = (1e9) * 2 + 100;
const int MAXN = (1e5) + 5;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;

// #define int ll

struct segTree
{
    vector<int> tree;
    int sz = 0;

    void init(int n)
    {
        sz = n;
        tree.resize(2 * sz, 0);
    }

    void set(int pos, int val)
    {
        pos += sz;
        tree[pos] = max(tree[pos], val);
        pos >>= 1;

        while (pos)
        {
            tree[pos] = max(tree[pos * 2], tree[pos * 2 + 1]);
            pos >>= 1;
        }
    }

    int get(int l, int r)
    {
        l += sz;
        r += sz;
        int res = 0;
        while (l < r)
        {
            if (l & 1)
                res = max(res, tree[l++]);
            if (r & 1)
                res = max(res, tree[--r]);
            l >>= 1;
            r >>= 1;
        }

        return res;
    }
};

struct test
{
    struct query
    {
        int l, k, id;
    };

    void solve(int testcase)
    {
        boost();

        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        cin >> a;

        vector<vector<query>> qrs(n);
        for (int i = 0; i < m; ++i)
        {
            int l, r, k;
            cin >> l >> r >> k;
            --l, --r;
            qrs[r].pb({l, k, i});
        }
        vector<int> ans(m);
        stack<int> vals;

        segTree tree;
        tree.init(n);
        stack<int> poses;

        for (int i = 0; i < n; ++i)
        {
            while (poses.size() and a[poses.top()] <= a[i])
                poses.pop();

            if (poses.size())
            {
                int el = poses.top();
                tree.set(el, a[i] + a[el]);
            }

            for (auto q : qrs[i])
            {
                int res = tree.get(q.l, i + 1);
                ans[q.id] = (int)(q.k >= res);
            }

            poses.push(i);
        }

        cout << ans << "\n";
    }
};

main()
{
    boost();
    int q = 1;
    // cin >> q;
    for (int i = 0; i < q; i++)
    {
        test t;
        t.solve(i);
    }
    return 0;
}
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//
//                                                                                    //
//                               Coded by Der_Vlἀpos                                  //
//                                                                                    //
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//

Compilation message

sortbooks.cpp:193:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  193 | main()
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 4 ms 840 KB Output is correct
15 Correct 5 ms 860 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 3 ms 756 KB Output is correct
18 Correct 3 ms 604 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1163 ms 95112 KB Output is correct
2 Correct 1275 ms 96052 KB Output is correct
3 Correct 1117 ms 96112 KB Output is correct
4 Correct 1204 ms 96048 KB Output is correct
5 Correct 1089 ms 96176 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8736 KB Output is correct
2 Correct 53 ms 8280 KB Output is correct
3 Correct 51 ms 8408 KB Output is correct
4 Correct 47 ms 8556 KB Output is correct
5 Correct 59 ms 8456 KB Output is correct
6 Correct 42 ms 8020 KB Output is correct
7 Correct 39 ms 8020 KB Output is correct
8 Correct 54 ms 8256 KB Output is correct
9 Correct 27 ms 3860 KB Output is correct
10 Correct 73 ms 7992 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 4 ms 840 KB Output is correct
15 Correct 5 ms 860 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 3 ms 756 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 159 ms 19284 KB Output is correct
20 Correct 137 ms 19540 KB Output is correct
21 Correct 141 ms 18756 KB Output is correct
22 Correct 127 ms 18716 KB Output is correct
23 Correct 147 ms 18704 KB Output is correct
24 Correct 144 ms 18628 KB Output is correct
25 Correct 139 ms 18492 KB Output is correct
26 Correct 143 ms 18912 KB Output is correct
27 Correct 136 ms 18924 KB Output is correct
28 Correct 158 ms 19116 KB Output is correct
29 Correct 121 ms 19480 KB Output is correct
30 Correct 171 ms 19424 KB Output is correct
31 Correct 138 ms 19588 KB Output is correct
32 Correct 148 ms 19420 KB Output is correct
33 Correct 149 ms 19332 KB Output is correct
34 Correct 95 ms 18124 KB Output is correct
35 Correct 85 ms 18244 KB Output is correct
36 Correct 100 ms 18004 KB Output is correct
37 Correct 93 ms 18032 KB Output is correct
38 Correct 98 ms 18120 KB Output is correct
39 Correct 107 ms 17672 KB Output is correct
40 Correct 92 ms 14156 KB Output is correct
41 Correct 134 ms 17160 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 4 ms 840 KB Output is correct
15 Correct 5 ms 860 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 3 ms 756 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 1163 ms 95112 KB Output is correct
20 Correct 1275 ms 96052 KB Output is correct
21 Correct 1117 ms 96112 KB Output is correct
22 Correct 1204 ms 96048 KB Output is correct
23 Correct 1089 ms 96176 KB Output is correct
24 Correct 67 ms 8736 KB Output is correct
25 Correct 53 ms 8280 KB Output is correct
26 Correct 51 ms 8408 KB Output is correct
27 Correct 47 ms 8556 KB Output is correct
28 Correct 59 ms 8456 KB Output is correct
29 Correct 42 ms 8020 KB Output is correct
30 Correct 39 ms 8020 KB Output is correct
31 Correct 54 ms 8256 KB Output is correct
32 Correct 27 ms 3860 KB Output is correct
33 Correct 73 ms 7992 KB Output is correct
34 Correct 159 ms 19284 KB Output is correct
35 Correct 137 ms 19540 KB Output is correct
36 Correct 141 ms 18756 KB Output is correct
37 Correct 127 ms 18716 KB Output is correct
38 Correct 147 ms 18704 KB Output is correct
39 Correct 144 ms 18628 KB Output is correct
40 Correct 139 ms 18492 KB Output is correct
41 Correct 143 ms 18912 KB Output is correct
42 Correct 136 ms 18924 KB Output is correct
43 Correct 158 ms 19116 KB Output is correct
44 Correct 121 ms 19480 KB Output is correct
45 Correct 171 ms 19424 KB Output is correct
46 Correct 138 ms 19588 KB Output is correct
47 Correct 148 ms 19420 KB Output is correct
48 Correct 149 ms 19332 KB Output is correct
49 Correct 95 ms 18124 KB Output is correct
50 Correct 85 ms 18244 KB Output is correct
51 Correct 100 ms 18004 KB Output is correct
52 Correct 93 ms 18032 KB Output is correct
53 Correct 98 ms 18120 KB Output is correct
54 Correct 107 ms 17672 KB Output is correct
55 Correct 92 ms 14156 KB Output is correct
56 Correct 134 ms 17160 KB Output is correct
57 Correct 1056 ms 96268 KB Output is correct
58 Correct 1004 ms 96460 KB Output is correct
59 Correct 965 ms 94668 KB Output is correct
60 Correct 887 ms 94676 KB Output is correct
61 Correct 876 ms 94628 KB Output is correct
62 Correct 939 ms 94776 KB Output is correct
63 Correct 550 ms 91584 KB Output is correct
64 Correct 498 ms 91588 KB Output is correct
65 Correct 756 ms 94772 KB Output is correct
66 Correct 925 ms 94484 KB Output is correct
67 Correct 856 ms 94592 KB Output is correct
68 Correct 942 ms 96212 KB Output is correct
69 Correct 1033 ms 96224 KB Output is correct
70 Correct 1000 ms 96000 KB Output is correct
71 Correct 1022 ms 95884 KB Output is correct
72 Correct 993 ms 96076 KB Output is correct
73 Correct 481 ms 87276 KB Output is correct
74 Correct 577 ms 88444 KB Output is correct
75 Correct 621 ms 87048 KB Output is correct
76 Correct 477 ms 87580 KB Output is correct
77 Correct 434 ms 87136 KB Output is correct
78 Correct 807 ms 88244 KB Output is correct
79 Correct 674 ms 64488 KB Output is correct
80 Correct 839 ms 87264 KB Output is correct