Data Structure Problem

Problem Description

using namespace std; const unsigned mul = 20190812; class Magic { public: Magic(unsigned state): state(state), ans(0) {} unsigned long long retrieve() { unsigned modulo = 0x7fffffff; state = ((unsigned long long) state * mul + ans) % modulo; unsigned high = state; state = ((unsigned long long) state * mul + ans) % modulo; return high * modulo + state; } int retrieve(int a, int b) { assert (a <= b); return (int) (retrieve() % (b - a + 1)) + a; } void submit(unsigned k) { ans = ans * mul + k; }

unsigned retrieveAns() { return ans; } private: unsigned state, ans; }; class DataStructure { public: DataStructure() { // The data structure is initially empty, until it's not. // Implement your initialization here. } void add(int x, int y) { // Add a 2D point (x, y) to the DS. // Implement your add here. } void erase(int r) { // Erase the r-th added point, of all the points that // have still not been erased. // Implement your erase here. } int size() { // Return how many points are still in the DS } pair<int, int> query() { // find two points p_i, p_j in the DS (not necessarily distinct), // such that the dot product of these two <p_i, p_j> (i <= j) // the smallest among all. Return (i, j). // If the DS is empty for now, return (0, 0). // Implement your query here. // If there are multiple (i, j) satisfying the condition, output the lexicographically smallest pair. } }; int main() { const int lim = 1E9; int q; cin >> q; for (int k = 0; k < q; ++k) { unsigned state; cin >> state; string s; cin >> s; DataStructure ds; Magic magic(state); for (char c: s) { if (c == 'a') { // add one point int x = magic.retrieve(-lim, lim); int y = magic.retrieve(-lim, lim); ds.add(x, y); } else if (c == 'e') { // select the lucky point unsigned pos = magic.retrieve(1, ds.size()); ds.erase(pos); } else if (c == 'q') { // query global minimum auto best = ds.query(); magic.submit(best.first); magic.submit(best.second); } } cout << magic.retrieveAns() << endl; } }

Input

The input format is a little different from traditional. Instead of giving a large file of input, the input is produced by the program above in a protocol. Thus reading the code and getting what it's doing is a fundamental step to solve this problem. The code is provided only in C++, but you should be easily converted into other languages. As you probably have seen, the program implements a protocol to generate the input data, based on some seeds (or input of input, if you like). The program reads from standard input: in the first line an integer $t$ ($1 \le t \le 20$), which is the number of test cases; then $t$ cases, each in two lines: first the integer state, which is between $10$ and $10^7$, inclusive; then follows a non-empty string of "aeq" of length no greater than $10^5$. "a" means add, "e" means erase and "q" means query. You would always find something to erase, i.e., we guarantee we will not try to erase from an empty data structure.

Output

Follow the practice of the given code for the output. Here are some hints for the sample below. Dot product of two points $p$ and $q$, is here, defined as the dot product from $0$ to $p$ and $0$ to $q$. Specifically, if $p=(a, b)$, $q=(c, d)$, dot product of $p$ and $q$ is $ac+bd$. For sample input one, the queries are:

• Query: return $(0, 0)$.
• Add 1st point: $(518204527, -960426430)$.
• Query: return $(1, 1)$. The answer is $20190812 \cdot 1 + 1 = 20190813$. For sample input two, the modifications and queries are:
• Add 1st point: $(-258558241, -773369213)$.
• Query: return $(1, 1)$.
• Add 2nd point: $(150662440, -65439273)$.
• Query: return $(1, 2)$.
• Add 3rd point: $(-888171126, -337111254)$.
• Erase 3rd point added among all still alive, so 3rd was erased.
• Query: return $(1, 2)$.
• Add 4th point: $(-470261300, 657949534)$.
• Add 5th point: $(-592507383, 366158932)$.
• Add 6th point: $(635425367, 329355360)$.
• Query: return $(1, 6)$.
• Add 7th point: $(900114299, 534416578)$.
• Erase 5th point added among all still alive, so 6th was erased.
• Query: return $(1, 7)$.
• Erase 2nd point added among all still alive, so 2nd was erased.
• Query: return $(1, 7)$. Sample input three decodes to be as follows:
• Add 1st point: $(-457246811, -252726229)$.
• Add 2nd point: $(-815357226, 987160210)$.
• Add 3rd point: $(689370621, -861950583)$.
• Add 4th point: $(-850699215, -38670848)$.
• Add 5th point: $(187488045, -980321149)$.
• Add 6th point: $(217752313, -264046720)$.
• Query: return $(2, 3)$.
• Erase 2nd point added among all still alive, so 2nd was erased.
• Query: return $(3, 4)$.
• Erase 3rd point added among all still alive, so 4th was erased.
• Query: return $(1, 3)$.
• Erase 1st point added among all still alive, so 1st was erased.
• Query: return $(6, 6)$.
• Erase 3rd point added among all still alive, so 6th was erased.
• Query: return $(3, 5)$.
• Erase 1st point added among all still alive, so 3rd was erased.
• Query: return $(5, 5)$.
• Erase 1st point added among all still alive, so 5th was erased.
• Query: return $(0, 0)$.

Sample Input

3

42

qaq

84

aqaqaeqaaaqaeqeq

9102

aaaaaaqeqeqeqeqeqeq

Sample Output

20190813

2668638611

549902096

Source

2019 Multi-University Training Contest 7