Lucky Numbers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define SZ(v) ((int)(v.size()))
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using indexed_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
constexpr int N = 2e6+9;
bool isLucky [N] = {false};
constexpr int MAX = 8388608+9; // interval[2 ^ log2(N) + 2]
int interval[MAX];
int build (int st = 0, int ed = N - 1, int parent = 1) {
    if (st == ed) return interval[parent] = 1;
    return interval[parent] = build(st, (st + ed) / 2, 2 * parent) + build((st + ed) / 2 + 1, ed, 2 * parent + 1);
}
int insert (int num, int st = 0, int ed = N - 1, int parent = 1) {
    interval[parent]++;
    if (st == ed)
        return interval[parent] - 1;
    if (num <= (st + ed) / 2) {
        return insert(num, st, (st + ed) / 2, 2 * parent);
    }
    return interval[2 * parent] + insert(num, (st + ed) / 2 + 1, ed, 2 * parent + 1);
}
int delKth (int kth, int st = 0, int ed = N - 1, int parent = 1) {
    interval[parent]--;
    if (st == ed)
        return st;
    if (interval[2 * parent] >= kth) {
        return delKth(kth, st, (st + ed) / 2, 2 * parent);
    }
    return delKth(kth - interval[2 * parent], (st + ed) / 2 + 1, ed, 2 * parent + 1);
}
int getKth (int kth, int st = 0, int ed = N - 1, int parent = 1) {
    if (st == ed)
        return st;
    if (interval[2 * parent] >= kth) {
        return getKth(kth, st, (st + ed) / 2, 2 * parent);
    }
    return getKth(kth - interval[2 * parent], (st + ed) / 2 + 1, ed, 2 * parent + 1);
}
int remove (int num, int st = 0, int ed = N - 1, int parent = 1) {
    interval[parent]--;
    if (st == ed)
        return interval[parent] + 1;
    if (num <= (st + ed) / 2)
        return remove(num, st, (st + ed) / 2, 2 * parent);
    return interval[2 * parent] + remove(num, (st + ed) / 2 + 1, ed, 2 * parent + 1);
}
int displayElements (int st = 0, int ed = N - 1, int parent = 1) {
    if (st < ed) {
        displayElements(st, (st + ed) / 2, 2 * parent);
        displayElements((st + ed) / 2 + 1, ed, 2 * parent + 1);
    }
    if (st == ed) {
        int count = interval[parent];
        while (count--) {
            cout << st << " ";
        }
    }
}
void pre_process () {
    for (int i = 1; i < N; i += 2)
        insert(i);
    isLucky[1] = true;
    int available = 1000000; // (2e6 / 2) = 1e6
    for (int start = 2; start <= available; ++start) {
        int next = 1, term = getKth(start), deleted = 0;
        isLucky[term] = true;
        while (term * next - deleted <= available) {
            delKth(term * next - deleted);
            deleted++;
            next++;
            available--;
        }
    }
}
void run () {
    int n;
    while (cin >> n) {
        int mid = n / 2;
        bool found = false;
        if (n % 2 == 0) {
            for (int k = mid; k > 0; k--) {
                if (isLucky[k] && isLucky[n - k]) {
                    cout << n << " is the sum of " << k << " and " << n - k << ".\n";
                    found = true;
                    break;
                }
            }
         }
        if (not found) cout << n << " is not the sum of two luckies!\n";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    pre_process();
//    freopen("/home/hamoudi/Coding/run.in", "r", stdin);
    int tt = 1;
//    cin >> tt;
    while (tt--)
        run();
    return 0;
}