oj.uz

Submission #958437

# Submission time Handle Problem Language Result Execution time Memory
958437 2024-04-05T19:18:05 Z I_am_Polish_Girl Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 2332 ms 190760 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>

using namespace std;

#define int long long

int log_ = 10;
int inf = 1000000000000000000;
int mod = 998244353;

struct segment_tree
{
    vector <int> b;
    vector <int> pr;
    vector <int> mx;

    vector <int> mx_pr;
    vector <int> mn_pr;


    int s = 1;

    void init(int n)
    {

        while (s < n)
            s *= 2;

        b.resize(2 * s);
        pr.resize(2 * s , -1);
        mx.resize(2 * s);
        mx_pr.resize(2 * s , -1);
        mn_pr.resize(2 * s, -1);

    }

    void push(int ind)
    {
        if (pr[ind] == -1)
            return;

        pr[ind * 2 + 1] = pr[ind];

        mx[ind * 2 + 1] = pr[ind * 2 + 1] + b[ind * 2 + 1];
 
        mx_pr[ind * 2 + 1] = pr[ind];

        pr[ind * 2 + 2] = pr[ind];

        mx[ind * 2 + 2] = pr[ind * 2 + 2] + b[ind * 2 + 2];

        mx_pr[ind * 2 + 2] = pr[ind];

        mn_pr[ind * 2 + 1] = pr[ind];
        mn_pr[ind * 2 + 2] = pr[ind];

        pr[ind] = -1;
    }

    void build(int ind, int l, int r, vector <int>& a)
    {
        if (r - l == 1)
        {
            if (l < a.size())
            {
                b[ind] = a[l];
                
                mx_pr[ind] = -1;

                mn_pr[ind] = -1;

                mx[ind] = 0;
            }
            else
            {
                b[ind] = -inf;
            }
            return;
        }

        int m = (l + r) / 2;

        build(ind * 2 + 1, l, m, a);
        build(ind * 2 + 2, m, r, a);

        b[ind] = max(b[ind * 2 + 1], b[ind * 2 + 2]);
        mx[ind] = max(mx[ind * 2 + 1], mx[ind * 2 + 2]);
    }


    void build(vector <int>& a)
    {
        build(0, 0, s, a);
    }

    void modif(int ind, int l, int r, int rx, int x)
    {
        if (l >= rx)
            return;


        if (r > rx)
        {

            push(ind);

            int m = (l + r) / 2;
            modif(ind * 2 + 1, l, m, rx, x);
            modif(ind * 2 + 2, m, r, rx, x);


            mx[ind] = max(mx[ind * 2 + 1], mx[ind * 2 + 2]);

            mx_pr[ind] = max(mx_pr[ind * 2 + 1], mx_pr[ind * 2 + 2]);
            
            mn_pr[ind] = min(mn_pr[ind * 2 + 1], mn_pr[ind * 2 + 2]);

            return;
        }

        if (mx_pr[ind] <= x)
        {
            pr[ind] = x;

            mx[ind] = b[ind] + x;

            mx_pr[ind] = x;

            mn_pr[ind] = x;

            return;
        }

        if (mn_pr[ind] > x)
        {
            return;
        }

        push(ind);

        int m = (l + r) / 2;
        modif(ind * 2 + 1, l, m, rx, x);
        modif(ind * 2 + 2, m, r, rx, x);


        mx[ind] = max(mx[ind * 2 + 1], mx[ind * 2 + 2]);

        mx_pr[ind] = max(mx_pr[ind * 2 + 1], mx_pr[ind * 2 + 2]);

        mn_pr[ind] = min(mn_pr[ind * 2 + 1], mn_pr[ind * 2 + 2]);
    }

    void modif(int rx, int x)
    {
        modif(0, 0, s, rx, x);
    }

    int get(int ind, int l, int r, int lx, int rx)
    {
        if ((lx <= l) and (r <= rx))
            return mx[ind];

        if ((rx <= l) or (r <= lx))
            return -inf;

        push(ind);

        int m = (l + r) / 2;

        int g1 = get(ind * 2 + 1, l, m, lx, rx);
        int g2 = get(ind * 2 + 2, m, r, lx, rx);

        return max(g1, g2);
    }

    int get(int lx, int rx)
    {
        return get(0, 0, s, lx, rx);
    }
};


signed main()
{
    ios_base::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);


    int n, m;
    cin >> n >> m;

    vector <int> a(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];

    segment_tree st;
    st.init(n);

    st.build(a);

    vector < vector <pair <int, int>> > q(n);


    vector <int> k(m);
    for (int i = 0; i < m; i++)
    {
        int l, r;
        cin >> l >> r >> k[i];
        
        l--;
        r--;

        q[r].push_back({ l , i });
    }

    vector <int> ans(m);



    stack <int> st_;



    for (int i = 0; i < n; i++)
    {

        while ((st_.size() > 0) and (a[st_.top()] <= a[i]))
            st_.pop();


        if (st_.size() != 0)
        {
            int ind = st_.top();

            st.modif(ind + 1, a[i]);
        }

        for (int j = 0; j < q[i].size(); j++)
        {
            int l = q[i][j].first;
            int ind = q[i][j].second;

            ans[ind] = st.get(l, i + 1);
        }


        st_.push(i);
    }


    for (int i = 0; i < m; i++)
    {

        //cout << ans[i] << "\n";
        
        
        if (ans[i] <= k[i])
            cout << 1 << "\n";
        else
            cout << 0 << "\n";
        
    }
}

/*

6 6
5 5 5 5 1 10
1 2
1 3
1 4
4 5
5 6
4 6
*/

Compilation message

sortbooks.cpp: In member function 'void segment_tree::build(long long int, long long int, long long int, std::vector<long long int>&)':
sortbooks.cpp:75:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             if (l < a.size())
      |                 ~~^~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:251:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |         for (int j = 0; j < q[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 344 KB Output is correct
5 Correct 1 ms 344 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 348 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 0 ms 348 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 344 KB Output is correct
5 Correct 1 ms 344 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 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 4 ms 836 KB Output is correct
12 Correct 5 ms 1372 KB Output is correct
13 Correct 6 ms 1492 KB Output is correct
14 Correct 8 ms 1628 KB Output is correct
15 Correct 8 ms 1456 KB Output is correct
16 Correct 6 ms 1372 KB Output is correct
17 Correct 5 ms 1116 KB Output is correct
18 Correct 6 ms 1372 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2242 ms 157612 KB Output is correct
2 Correct 2190 ms 157508 KB Output is correct
3 Correct 2221 ms 157684 KB Output is correct
4 Correct 2228 ms 157468 KB Output is correct
5 Correct 1790 ms 157512 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 18000 KB Output is correct
2 Correct 127 ms 19892 KB Output is correct
3 Correct 131 ms 20052 KB Output is correct
4 Correct 108 ms 19992 KB Output is correct
5 Correct 119 ms 19964 KB Output is correct
6 Correct 98 ms 19664 KB Output is correct
7 Correct 103 ms 19644 KB Output is correct
8 Correct 114 ms 19400 KB Output is correct
9 Correct 65 ms 5460 KB Output is correct
10 Correct 109 ms 19396 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 344 KB Output is correct
5 Correct 1 ms 344 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 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 4 ms 836 KB Output is correct
12 Correct 5 ms 1372 KB Output is correct
13 Correct 6 ms 1492 KB Output is correct
14 Correct 8 ms 1628 KB Output is correct
15 Correct 8 ms 1456 KB Output is correct
16 Correct 6 ms 1372 KB Output is correct
17 Correct 5 ms 1116 KB Output is correct
18 Correct 6 ms 1372 KB Output is correct
19 Correct 354 ms 42320 KB Output is correct
20 Correct 346 ms 42344 KB Output is correct
21 Correct 304 ms 41936 KB Output is correct
22 Correct 316 ms 42064 KB Output is correct
23 Correct 314 ms 41864 KB Output is correct
24 Correct 256 ms 41808 KB Output is correct
25 Correct 265 ms 41856 KB Output is correct
26 Correct 267 ms 42072 KB Output is correct
27 Correct 325 ms 42068 KB Output is correct
28 Correct 278 ms 42040 KB Output is correct
29 Correct 294 ms 42300 KB Output is correct
30 Correct 284 ms 42360 KB Output is correct
31 Correct 284 ms 42312 KB Output is correct
32 Correct 290 ms 42436 KB Output is correct
33 Correct 297 ms 42324 KB Output is correct
34 Correct 274 ms 41264 KB Output is correct
35 Correct 240 ms 41404 KB Output is correct
36 Correct 249 ms 41084 KB Output is correct
37 Correct 240 ms 41180 KB Output is correct
38 Correct 247 ms 41300 KB Output is correct
39 Correct 270 ms 40776 KB Output is correct
40 Correct 197 ms 27068 KB Output is correct
41 Correct 289 ms 40128 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 344 KB Output is correct
5 Correct 1 ms 344 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 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 4 ms 836 KB Output is correct
12 Correct 5 ms 1372 KB Output is correct
13 Correct 6 ms 1492 KB Output is correct
14 Correct 8 ms 1628 KB Output is correct
15 Correct 8 ms 1456 KB Output is correct
16 Correct 6 ms 1372 KB Output is correct
17 Correct 5 ms 1116 KB Output is correct
18 Correct 6 ms 1372 KB Output is correct
19 Correct 2242 ms 157612 KB Output is correct
20 Correct 2190 ms 157508 KB Output is correct
21 Correct 2221 ms 157684 KB Output is correct
22 Correct 2228 ms 157468 KB Output is correct
23 Correct 1790 ms 157512 KB Output is correct
24 Correct 148 ms 18000 KB Output is correct
25 Correct 127 ms 19892 KB Output is correct
26 Correct 131 ms 20052 KB Output is correct
27 Correct 108 ms 19992 KB Output is correct
28 Correct 119 ms 19964 KB Output is correct
29 Correct 98 ms 19664 KB Output is correct
30 Correct 103 ms 19644 KB Output is correct
31 Correct 114 ms 19400 KB Output is correct
32 Correct 65 ms 5460 KB Output is correct
33 Correct 109 ms 19396 KB Output is correct
34 Correct 354 ms 42320 KB Output is correct
35 Correct 346 ms 42344 KB Output is correct
36 Correct 304 ms 41936 KB Output is correct
37 Correct 316 ms 42064 KB Output is correct
38 Correct 314 ms 41864 KB Output is correct
39 Correct 256 ms 41808 KB Output is correct
40 Correct 265 ms 41856 KB Output is correct
41 Correct 267 ms 42072 KB Output is correct
42 Correct 325 ms 42068 KB Output is correct
43 Correct 278 ms 42040 KB Output is correct
44 Correct 294 ms 42300 KB Output is correct
45 Correct 284 ms 42360 KB Output is correct
46 Correct 284 ms 42312 KB Output is correct
47 Correct 290 ms 42436 KB Output is correct
48 Correct 297 ms 42324 KB Output is correct
49 Correct 274 ms 41264 KB Output is correct
50 Correct 240 ms 41404 KB Output is correct
51 Correct 249 ms 41084 KB Output is correct
52 Correct 240 ms 41180 KB Output is correct
53 Correct 247 ms 41300 KB Output is correct
54 Correct 270 ms 40776 KB Output is correct
55 Correct 197 ms 27068 KB Output is correct
56 Correct 289 ms 40128 KB Output is correct
57 Correct 2332 ms 190560 KB Output is correct
58 Correct 2325 ms 190548 KB Output is correct
59 Correct 2076 ms 189392 KB Output is correct
60 Correct 1991 ms 189696 KB Output is correct
61 Correct 2068 ms 189780 KB Output is correct
62 Correct 2099 ms 189644 KB Output is correct
63 Correct 1306 ms 187240 KB Output is correct
64 Correct 1293 ms 187320 KB Output is correct
65 Correct 1692 ms 189620 KB Output is correct
66 Correct 1703 ms 189512 KB Output is correct
67 Correct 1687 ms 189320 KB Output is correct
68 Correct 1738 ms 190760 KB Output is correct
69 Correct 1777 ms 190620 KB Output is correct
70 Correct 1783 ms 190108 KB Output is correct
71 Correct 1730 ms 190320 KB Output is correct
72 Correct 1734 ms 190464 KB Output is correct
73 Correct 1235 ms 182316 KB Output is correct
74 Correct 1253 ms 182884 KB Output is correct
75 Correct 1275 ms 182568 KB Output is correct
76 Correct 1233 ms 182628 KB Output is correct
77 Correct 1247 ms 181692 KB Output is correct
78 Correct 1584 ms 182316 KB Output is correct
79 Correct 1126 ms 119420 KB Output is correct
80 Correct 1687 ms 179316 KB Output is correct