Zi7PFwYG

1#include <iostream>
2#include <utility>
3#include <vector>
4#include <algorithm>
5#include <fstream>
6
7using namespace std;
8
9struct Warrior {
10    int m, p, t;
11    int index;
12};
13
14struct Oracle {
15    int m, p, t;
16    int count_changes;
17    vector<Warrior> Fenix;
18};
19void build(vector<Oracle> &tree, int node, int tl, int tr);
20Oracle get_max(vector<Oracle> &tree, int node, int l, int r, int tl, int tr);
21void update(vector<Oracle> &tree, int node, int tl, int tr, int pos, int new_val, int main_val, Warrior warrior);
22int power_2(int x);
23
24bool main_cmp(const Warrior& a, const Warrior& b) // m
25{
26    return a.m < b.m;
27}
28
29bool template_cmp(const Warrior& a, const Warrior& b) // p
30{
31    return a.p < b.p;
32}
33
34int main()
35{
36    ifstream fin("input.txt");
37    ofstream fout("output.txt");
38
39    int n;
40    fin >> n;
41
42    vector<Warrior> men (n); // {m[i], indexes in begin order, t[i], p[i]}
43    vector<int> ap (n); // for argsort by p
44    vector<bool> cand (n); // true candidators
45    vector<Oracle> tree (n * 4); // segment tree
46
47    int n_2 = power_2(n);
48
49    for (int i = 0; i < n; i++)
50    {
51        fin >> men[i].m >> men[i].p >> men[i].t;  // m[i] >> p[i] >> t[i]
52        men[i].index = i; //begin order of indexes
53    }
54    fin.close();
55
56    sort(men.begin(), men.end(), template_cmp); //sort by p for argsort --> compression of values
57
58    //argsort for p -> for example {32, 45, 2, 2, 7} => {3, 4, 0, 0, 2}
59    for (int i = 0; i < n; i++)
60    {
61        if (i != 0 && men[i].p == men[i - 1].p)
62        {
63            ap[i] = ap[i - 1];
64        }
65        else
66        {
67            ap[i] = i;
68        }
69
70    }
71    for (int i = 0; i < n; i++)
72    {
73        men[i].p = ap[i];
74    }
75    // end argsort
76
77    sort(men.begin(), men.end(), main_cmp); //sort by m
78
79    build(tree, 0, 0, n_2 - 1); //segment tree from size_array by -1 value
80
81    //key part
82    Oracle max_t, max_t_right, max_t_left; // max_t - parent and kids/near max el -> right and left
83
84    for (int i = n - 1; i >= 0; i--)
85    {
86        max_t = get_max(tree, 0, men[i].p, men[i].p, 0, n_2 - 1);
87
88        if (max_t.t < men[i].t)
89        {
90            update(tree, 0, 0, n_2 - 1, men[i].p, men[i].t, men[i].m, men[i]);
91        }
92
93        max_t = get_max(tree, 0, (men[i].p + 1) % n_2, n_2 - 1, 0, n_2 - 1);
94
95        if (max_t.t > men[i].t && max_t.p > men[i].p && max_t.m > men[i].m)
96        {
97            cand[men[i].index] = true;
98        } else {
99            max_t_right = get_max(tree, 0, (max_t.p + 1) % n_2, n_2 - 1, 0, n_2 - 1);
100            if (max_t_right.t > men[i].t && max_t_right.p > men[i].p && max_t_right.m > men[i].m)
101            {
102                cand[men[i].index] = true;
103            } else {
104                max_t_left = get_max(tree, 0, (men[i].p + 1) % n_2, max_t.p - 1, 0, n_2 - 1);
105                if (max_t_left.t > men[i].t && max_t_left.p > men[i].p && max_t_left.m > men[i].m)
106                {
107                    cand[men[i].index] = true;
108                } else {
109                    for (int j = 0; j < max_t.count_changes; j++)
110                    {
111                        if (max_t.Fenix[j].m > men[i].m && max_t.Fenix[j].t > men[i].t && max_t.Fenix[j].p > men[i].p)
112                        {
113                            cand[men[i].index] = true;
114                        }
115                    }
116                }
117            }
118        }
119    }
120
121    // output
122    for (int i = 0; i < n; i++)
123    {
124        if (cand[i] == false)
125        {
126            fout << i + 1 << ' ';
127        }
128    }
129
130    fout.close();
131
132    return 0;
133}
134
135int power_2(int x)
136{
137    int p2 = 1;
138    while (true)
139    {
140        if (p2 >= x)
141            return p2;
142        p2<<=1;
143    }
144}
145
146void build(vector<Oracle> &tree, int node, int tl, int tr)
147{
148    if (tl == tr)
149    {
150        tree[node].count_changes = 0;
151        tree[node].m = -1;
152        tree[node].t = -1;
153        tree[node].p = -1;
154    }
155    else
156    {
157        int m = (tr + tl) / 2;
158        build(tree, node * 2 + 1, tl, m);
159        build(tree, node * 2 + 2, m + 1, tr);
160        tree[node] = tree[node * 2 + 1].t > tree[node * 2 + 2].t ?
161                     tree[node * 2 + 1] : tree[node * 2 + 2];
162    }
163}
164
165Oracle get_max(vector<Oracle> &tree, int node, int l, int r, int tl, int tr)
166{
167    if (l > r)
168    {
169        return {-1};
170    }
171    if(l == tl && r == tr)
172    {
173        return tree[node];
174    }
175    int tm = (tr + tl) / 2;
176    Oracle m1 = get_max(tree, node * 2 + 1, l, min(tm, r), tl, tm);
177    Oracle m2 = get_max(tree, node * 2 + 2, max(l, tm+1), r, tm + 1, tr);
178    return m1.t > m2.t ? m1 : m2;
179}
180
181void update(vector<Oracle> &tree, int node, int tl, int tr, int pos, int new_val, int main_val, Warrior warrior)
182{
183    if (tl == tr)
184    {
185        tree[node].Fenix.push_back(warrior);
186        tree[node].count_changes++;
187        tree[node].m = main_val;
188        tree[node].t = new_val;
189        tree[node].p = pos;
190    }
191    else
192    {
193        int m = (tr + tl) / 2;
194        if (pos <= m)
195        {
196            update(tree, node * 2 + 1, tl, m, pos, new_val, main_val, warrior);
197        }
198        else
199        {
200            update(tree, node * 2 + 2, m + 1, tr, pos, new_val, main_val, warrior);
201        }
202        tree[node] = tree[node * 2 + 1].t > tree[node * 2 + 2].t ?
203                     tree[node * 2 + 1] : tree[node * 2 + 2];
204    }
205}