3755: 我是 A 题(第六轮01)
题目描述
有一些三元组 (a, b, c)，满足a, b, c ∈ ℤ , a ∈ [1, A]， b ∈ [1, B]， c ∈ [1, C]。
定义一个三元组(a1, b1, c1 ) 不大于另一个三元组 (a2, b2, c2 )，当且仅当a1 ≤ a2， b1 ≤ b2， c1 ≤ c2 。
一共有 n 次操作，每次给出一个三元组 (u, v, w)，将现存三元组中所有不大于 (u, v, w) 的删除。
问经过 n 次操作后一共删掉了多少个三元组。
因为本题输入量过大，所以采用题内生成数据的方式。
具体来说，选手需将以下代码片段粘贴至上交的代码中： const int N = 3e7 + 10;
typedef unsigned long long ull;
int n, A, B, C, u[N], v[N], w[N];
ull Rand (ull &k1, ull &k2) { ull k3 = k1, k4 = k2; k1 = k4;
k3 ^= (k3 << 23);
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26); return k2 + k4;
}
void GetData () {
ull x, y;
cin >> n >> A >> B >> C >> x >> y; for (int i = 1; i <= n; i++) {
u[i] = Rand(x, y) % A + 1;
v[i] = Rand(x, y) % B + 1;
w[i] = Rand(x, y) % C + 1;
if (Rand(x, y) % 3 == 0) u[i] = A; if (Rand(x, y) % 3 == 0) v[i] = B;
if ((u[i] != A) && (v[i] != B)) w[i] = C; }
}
并在 ′main()′ 函数的开头调用 ′ GetData()′ 以获取数据。
调用 ′ GetData()′ 函数后，本题输入数据将会保存在变量 n, A, B, C, ui, vi, wi 中， 其含义见题目描述。
请选手仔细观察给出的数据生成器，数据生成方式与解题强相关。
输入
【输入格式】
六个以空格分隔的正整数 n, A, B, C, x, y。
输出
【输出格式】
一个数表示答案。
样例输入 复制
2 10 10 10 114514 1919810样例输出 复制
693提示
【数据范围】
对于测试点 1 ∼ 2，保证 n ⩽ 10, A, B, C ⩽ 100。
对于测试点 3 ∼ 6，保证 n ⩽ 105 , A, B, C ⩽ 100。
对于测试点 7 ∼ 8，保证 n ⩽ 1000, A, B, C ⩽ 1000。
对于测试点 9，保证 n ⩽ 1000, A, B, C ⩽ 10^5 。
对于测试点 10，保证 n ⩽ 105, A, B, C ⩽ 10^5
对于测试点 11，保证 n ⩽ 105, A, B, C ⩽ 10^6 。
对于测试点 12 ∼ 13，保证 n ⩽ 106, A, B, C ⩽ 10^6 。
对于测试点 14 ∼ 15，保证 n ⩽ 107, A, B, C ⩽ 10^6 。 对于测试点 16 ∼ 18，保证 n ⩽ 10^7, A, B, C ⩽ 10^7 。
对于测试点 19 ∼ 20，保证 n ⩽ 3 × 10^7 , A, B, C ⩽ 3 × 10^7 。
对于所有测试点，保证 0 ⩽ x, y ⩽ 10^18 。