244222026-02-11 13:50:57miszorimarciKedvenc számokcpp17Accepted 100/100954ms63800 KiB
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 300005;
int N, M, Q;
int A[MAXN];
int fav_id[MAXN]; 
set<int> pos[MAXN]; 
multiset<int> head_gaps; 
int tree[4 * MAXN];

void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        tree[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) update(2 * node, start, mid, idx, val);
    else update(2 * node + 1, mid + 1, end, idx, val);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return max(query(2 * node, start, mid, l, r), query(2 * node + 1, mid + 1, end, l, r));
}

void add_gap(int a, int b) {
    if (a > b) return;
    if (a == 1) {
        head_gaps.insert(b);
        update(1, 1, N + 1, 1, *head_gaps.rbegin());
    } else {
        update(1, 1, N + 1, a, b);
    }
}

void remove_gap(int a, int b) {
    if (a > b) return;
    if (a == 1) {
        auto it = head_gaps.find(b);
        if (it != head_gaps.end()) head_gaps.erase(it);
        update(1, 1, N + 1, 1, head_gaps.empty() ? 0 : *head_gaps.rbegin());
    } else {
        update(1, 1, N + 1, a, 0);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> Q;
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= M; i++) {
        int b;
        cin >> b;
        fav_id[b] = i;
        pos[i].insert(0);
        pos[i].insert(N + 1);
    }

    for (int i = 1; i <= N; i++) {
        if (fav_id[A[i]]) {
            pos[fav_id[A[i]]].insert(i);
        }
    }

    for (int i = 1; i <= M; i++) {
        for (auto it = pos[i].begin(); next(it) != pos[i].end(); ++it) {
            add_gap(*it + 1, *next(it) - 1);
        }
    }

    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int k, x;
            cin >> k >> x;
            if (A[k] == x) continue;

            if (fav_id[A[k]]) {
                int id = fav_id[A[k]];
                auto it = pos[id].find(k);
                int pr = *prev(it), nx = *next(it);
                remove_gap(pr + 1, k - 1);
                remove_gap(k + 1, nx - 1);
                pos[id].erase(it);
                add_gap(pr + 1, nx - 1);
            }

            A[k] = x;

            if (fav_id[A[k]]) {
                int id = fav_id[A[k]];
                auto it = pos[id].insert(k).first;
                int pr = *prev(it), nx = *next(it);
                remove_gap(pr + 1, nx - 1);
                add_gap(pr + 1, k - 1);
                add_gap(k + 1, nx - 1);
            }
        } else {
            int l, r; cin >> l >> r;
            if (query(1, 1, N + 1, 1, l) >= r) cout << "NEM\n";
            else cout << "IGEN\n";
        }
    }

    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted14ms14388 KiB
2Accepted122ms20532 KiB
subtask210/10
3Accepted14ms14836 KiB
4Accepted14ms14644 KiB
5Accepted17ms14644 KiB
6Accepted17ms14836 KiB
7Accepted17ms14704 KiB
8Accepted17ms14684 KiB
9Accepted14ms14656 KiB
10Accepted14ms14572 KiB
11Accepted17ms14808 KiB
12Accepted14ms14644 KiB
13Accepted17ms14760 KiB
14Accepted14ms14644 KiB
15Accepted14ms14572 KiB
subtask315/15
16Accepted314ms32828 KiB
17Accepted513ms37692 KiB
18Accepted620ms44340 KiB
19Accepted954ms52880 KiB
20Accepted866ms63540 KiB
21Accepted451ms40756 KiB
22Accepted737ms44500 KiB
23Accepted708ms44340 KiB
subtask420/20
24Accepted317ms34108 KiB
25Accepted405ms38764 KiB
26Accepted479ms45468 KiB
27Accepted569ms53392 KiB
28Accepted760ms63800 KiB
29Accepted391ms41780 KiB
30Accepted469ms45504 KiB
31Accepted550ms45364 KiB
32Accepted338ms42356 KiB
33Accepted347ms47248 KiB
34Accepted374ms48792 KiB
35Accepted349ms44080 KiB
36Accepted395ms41728 KiB
37Accepted342ms43828 KiB
38Accepted344ms41524 KiB
subtask525/25
39Accepted14ms14836 KiB
40Accepted14ms14644 KiB
41Accepted17ms14644 KiB
42Accepted17ms14836 KiB
43Accepted17ms14704 KiB
44Accepted17ms14684 KiB
45Accepted14ms14656 KiB
46Accepted14ms14572 KiB
47Accepted17ms14808 KiB
48Accepted14ms14644 KiB
49Accepted17ms14760 KiB
50Accepted14ms14644 KiB
51Accepted14ms14572 KiB
52Accepted68ms18400 KiB
53Accepted82ms19016 KiB
54Accepted93ms20020 KiB
55Accepted130ms22112 KiB
56Accepted189ms27456 KiB
57Accepted104ms21188 KiB
58Accepted149ms22100 KiB
59Accepted133ms22068 KiB
60Accepted160ms22148 KiB
61Accepted108ms22320 KiB
62Accepted175ms27312 KiB
63Accepted162ms30200 KiB
64Accepted90ms21300 KiB
65Accepted86ms21824 KiB
66Accepted97ms22600 KiB
67Accepted93ms22776 KiB
68Accepted96ms24376 KiB
69Accepted87ms22836 KiB
70Accepted86ms22068 KiB
71Accepted93ms22924 KiB
72Accepted85ms22068 KiB
subtask630/30
73Accepted14ms14532 KiB
74Accepted137ms20692 KiB
75Accepted14ms14836 KiB
76Accepted14ms14644 KiB
77Accepted17ms14644 KiB
78Accepted17ms14836 KiB
79Accepted17ms14704 KiB
80Accepted17ms14684 KiB
81Accepted14ms14656 KiB
82Accepted14ms14572 KiB
83Accepted17ms14808 KiB
84Accepted14ms14644 KiB
85Accepted17ms14760 KiB
86Accepted14ms14644 KiB
87Accepted14ms14572 KiB
88Accepted68ms18400 KiB
89Accepted82ms19016 KiB
90Accepted93ms20020 KiB
91Accepted130ms22112 KiB
92Accepted189ms27456 KiB
93Accepted104ms21188 KiB
94Accepted149ms22100 KiB
95Accepted133ms22068 KiB
96Accepted160ms22148 KiB
97Accepted108ms22320 KiB
98Accepted175ms27312 KiB
99Accepted162ms30200 KiB
100Accepted90ms21300 KiB
101Accepted86ms21824 KiB
102Accepted97ms22600 KiB
103Accepted93ms22776 KiB
104Accepted96ms24376 KiB
105Accepted87ms22836 KiB
106Accepted86ms22068 KiB
107Accepted93ms22924 KiB
108Accepted85ms22068 KiB
109Accepted314ms32828 KiB
110Accepted513ms37692 KiB
111Accepted620ms44340 KiB
112Accepted954ms52880 KiB
113Accepted866ms63540 KiB
114Accepted451ms40756 KiB
115Accepted737ms44500 KiB
116Accepted708ms44340 KiB
117Accepted317ms34108 KiB
118Accepted405ms38764 KiB
119Accepted479ms45468 KiB
120Accepted569ms53392 KiB
121Accepted760ms63800 KiB
122Accepted391ms41780 KiB
123Accepted469ms45504 KiB
124Accepted550ms45364 KiB
125Accepted338ms42356 KiB
126Accepted347ms47248 KiB
127Accepted374ms48792 KiB
128Accepted349ms44080 KiB
129Accepted395ms41728 KiB
130Accepted342ms43828 KiB
131Accepted344ms41524 KiB
132Accepted230ms28620 KiB
133Accepted279ms31028 KiB
134Accepted367ms33860 KiB
135Accepted540ms38452 KiB
136Accepted778ms45200 KiB
137Accepted791ms53300 KiB
138Accepted883ms63748 KiB
139Accepted527ms41104 KiB
140Accepted679ms44880 KiB
141Accepted643ms45020 KiB
142Accepted635ms45052 KiB