MyLeetcode/cpp_solutions/3161.cpp at main · Kaminyou/MyLeetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
class SegTreeNode
{
    public:
    SegTreeNode* left = NULL;
    SegTreeNode* right = NULL;
    int start, end;
    int info;  // the maximum value of the range
    bool tag;

    SegTreeNode(int a, int b, int val)  // init for range [a,b] with val
    {
        tag = 0;
        start = a, end = b;
        if (a==b)
        {
            info = val;
            return;
        }
        int mid = (a+b)/2;
        if (left==NULL)
        {
            left = new SegTreeNode(a, mid, val);
            right = new SegTreeNode(mid+1, b, val);
            info = max(left->info, right->info);  // check with your own logic
        }
    }

    SegTreeNode(int a, int b, vector<int>& val)  // init for range [a,b] with the same-size array val
    {
        tag = 0;
        info = 0;
        start = a, end = b;
        if (a==b)
        {
            info = val[a];
            return;
        }
        int mid = (a+b)/2;
        if (left==NULL)
        {
            left = new SegTreeNode(a, mid, val);
            right = new SegTreeNode(mid+1, b, val);
            info = max(left->info, right->info);  // check with your own logic
        }
    }

    void pushDown()
    {
        if (tag==1 && left)
        {
            left->info = info;
            right->info = info;
            left->tag = 1;
            right->tag = 1;
            tag = 0;
        }
    }

    void updateRange(int a, int b, int val)     // set range [a,b] with val
    {
        if (b < start || a > end ) // not covered by [a,b] at all
            return;
        if (a <= start && end <=b)  // completely covered within [a,b]
        {
            info = val;
            tag = 1;
            return;
        }

        if (left)
        {
            pushDown();
            left->updateRange(a, b, val);
            right->updateRange(a, b, val);
            info = max(left->info, right->info);  // write your own logic
        }
    }

    int queryRange(int a, int b)     // query the maximum value within range [a,b]
    {
        if (b < start || a > end )
        {
            return INT_MIN/2;  // check with your own logic
        }
        if (a <= start && end <=b)
        {
            return info;  // check with your own logic
        }

        if (left)
        {
            pushDown();
            int ret = max(left->queryRange(a, b), right->queryRange(a, b));
            info = max(left->info, right->info);    // check with your own logic
            return ret;
        }

        return info;   // should not reach here
    }

};

class Solution {
public:
    vector<bool> getResults(vector<vector<int>>& queries) {
        int n = min(50000, (int)queries.size()*3) + 5;
        SegTreeNode* root = new SegTreeNode(0, n, 0);

        set<int> st;
        st.insert(0);
        vector<bool> res;
        for (auto& q : queries) {
            if (q[0] == 1) {
                int x = q[1];
                st.insert(x);
                auto iter = st.find(x);
                int a = *prev(iter);
                root->updateRange(x, x, x - a);
                if (next(iter) != st.end()) {
                    int b = *next(iter);
                    root->updateRange(b, b, b - x);
                }
            }
            else {
                int x = q[1];
                int sz = q[2];
                int len = root->queryRange(0, x);
                if (st.find(x) == st.end()) {
                    auto iter = st.lower_bound(x);
                    int a = *prev(iter);
                    len = max(len, x - a);
                }
                res.push_back(len >= sz);
            }
        }
        return res;
    }
};