map

struct mymap {
    static const int N=(1<<22);
    int key[N], val[N];

    int query(int x) {
        int i = x & (N - 1);
        while (key[i] != -1 && key[i] != x) i = (i + 1) & (N - 1);
        return val[i];
    }

    void update(int x, int id) {// can't find then return -1
        int i = x & (N - 1);
        while (key[i] != -1 && key[i] != x) i = (i + 1) & (N - 1);
        key[i] = x, val[i] = id;
    }

    void clear() {
        memset(key, -1, sizeof(key));
        memset(val, -1, sizeof(val));
    }
};