배낭과 쿼리

먼저 양의 정수 $MOD$가 주어진다. 처음에 배낭은 비어 있다.

$Q$개의 쿼리를 처리한다. 각 쿼리에서는 먼저 ADD 또는 REMOVE 연산 중 하나를 수행하고, 그다음 FIND 연산을 수행한다.

ADD 연산에서는 양의 정수 $w$와 $v$가 주어진다. 무게가 $w$이고 가치가 $v$인 쿠키를 배낭에 넣는다.

REMOVE 연산에서는 배낭에 있는 쿠키 중 무게가 가장 작은 쿠키를 꺼내 먹는다.

ADD 또는 REMOVE 연산 후에는 FIND 연산을 수행한다. 양의 정수 $l$과 $r$이 주어지면, 배낭에서 쿠키를 골라 $l \leq (X \bmod MOD) \leq r$을 만족하게 할 수 있는지 묻는다. 여기서 $X$는 고른 쿠키들의 무게 합이다. 만족하게 할 수 없으면 -1을 출력한다. 만족하게 할 수 있으면 고른 쿠키들의 가치 합의 최댓값을 출력한다.

입력은 다음 형식으로 주어진다.

$MOD$ $Q$ $t'_1$ $w'_1$ $v'_1$ $l'_1$ $r'_1$ $t'_2$ $w'_2$ $v'_2$ $l'_2$ $r'_2$ $\ldots$ $t'_Q$ $w'_Q$ $v'_Q$ $l'_Q$ $r'_Q$

쿼리는 암호화되어 있으며, 아래 방식으로 복호화한다. $t'_i, w'_i, v'_i, l'_i, r'_i$를 복호화하면 $t_i, w_i, v_i, l_i, r_i$를 얻는다.

$1 \leq w_i, v_i \leq 10^9$, $0 \leq l_i \leq r_i \leq MOD-1$이다. $t_i=1$은 ADD+FIND 쿼리이고, $t_i=2$는 REMOVE+FIND 쿼리이며 이때 $w_i=v_i=0$이다. ADD로 넣는 쿠키는 이전 ADD로 넣은 어떤 쿠키보다도 무겁다. REMOVE를 실행할 때 배낭은 비어 있지 않다.

복호화 과정은 다음과 같다.

• 먼저 Crypto 클래스의 인스턴스를 만든다.
• 각 쿼리마다 $t', w', v', l', r'$ 순서로 decode 함수를 호출한다. 반환값이 각각 $t, w, v, l, r$이다. 그다음 쿼리를 수행하고, FIND 결과를 인자로 query 함수를 호출한다.

Crypto 클래스의 코드와 사용 예시는 C++11 이상, Java, D, C#용으로 제공된다. 아래는 C++ 예시이다.

#include <cstdint> //uint8_t, uint32_t

class Crypto {
public:
    Crypto() {
        sm = cnt = 0;
        seed();
    }

    int decode(int z) {
        z ^= next();
        z ^= (next() << 8);
        z ^= (next() << 16);
        z ^= (next() << 22);
        return z;
    }

    void query(long long z) {
        const long long B = 425481007;
        const long long MD = 1000000007;
        cnt++;
        sm = ((sm * B % MD + z) % MD + MD) % MD;
        seed();
    }
private:
    long long sm;
    int cnt;

    uint8_t data[256];
    int I, J;

    void swap_data(int i, int j) {
        uint8_t tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    void seed() {
        uint8_t key[8];
        for (int i = 0; i < 4; i++) {
            key[i] = (sm >> (i * 8));
        }
        for (int i = 0; i < 4; i++) {
            key[i+4] = (cnt >> (i * 8));
        }

        for (int i = 0; i < 256; i++) {
            data[i] = i;
        }
        I = J = 0;

        int j = 0;
        for (int i = 0; i < 256; i++) {
            j = (j + data[i] + key[i%8]) % 256;
            swap_data(i, j);
        }
    }

    uint8_t next() {
        I = (I+1) % 256;
        J = (J + data[I]) % 256;
        swap_data(I, J);
        return data[(data[I] + data[J]) % 256];
    }
};

Crypto 클래스는 $Q = 100000$을 처리하는 데 약 200 정도 걸린다.

샘플 main 코드는 다음과 같다.

#include <cstdio>
#include <cstdlib>
#include <cstdint> //uint8_t, uint32_t

class Crypto {
    ...
};

int main() {
    int MOD, Q;
    scanf("%d %d", &MOD, &Q);
    Crypto c;
    for (int i = 0; i < Q; i++) {
        int t, w, v, l, r;
        scanf("%d %d %d %d %d", &t, &w, &v, &l, &r);
        t = c.decode(t);
        w = c.decode(w);
        v = c.decode(v);
        l = c.decode(l);
        r = c.decode(r);
        if (t == 1) {
            (add candy(w, v))
        } else {
            (delete candy)
        }
        long long ans = (answer for query(l, r));
        c.query(ans);
        printf("%lld\n", ans);
    }
}

각 쿼리마다 FIND 연산의 결과를 출력한다.

$0 \leq t'_i, w'_i, v'_i, l'_i, r'_i \leq 2^{30} - 1$, $2 \leq MOD \leq 500$, $1 \leq Q \leq 100000$.

예제 1을 복호화한 결과:

10
7
1 5 10 5 5
2 0 0 0 9
1 7 10 2 4
1 12 11 9 9
2 0 0 1 1
1 22 10 2 3
1 32 100 4 4

예제 2를 복호화한 결과:

7
20
1 5 44 0 1
1 11 90 0 3
2 0 0 3 4
1 18 68 1 6
1 25 32 2 3
1 31 22 2 3
1 32 26 1 5
1 36 31 3 6
2 0 0 2 5
1 43 10 3 6
2 0 0 5 6
2 0 0 3 4
2 0 0 2 4
2 0 0 1 5
2 0 0 3 5
1 49 48 0 4
2 0 0 1 5
1 50 36 0 6
1 56 48 3 5
1 59 17 3 5