結果
| 問題 |
No.2359 A in S ?
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:14:26 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,721 ms / 2,000 ms |
| コード長 | 9,806 bytes |
| コンパイル時間 | 1,122 ms |
| コンパイル使用メモリ | 104,420 KB |
| 実行使用メモリ | 133,628 KB |
| 最終ジャッジ日時 | 2025-05-14 13:15:49 |
| 合計ジャッジ時間 | 8,203 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 |
ソースコード
#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm> // For std::max, std::min
// Custom function for ceiling division: ceil(a / b)
// Assumes b > 0
long long ceil_div(long long a, long long b) {
// Standard C++ integer division truncates towards zero.
if (a >= 0) {
// For non-negative a, use standard formula (a + b - 1) / b
return (a + b - 1) / b;
} else {
// For negative a, standard division a / b effectively computes ceiling.
// E.g., -3 / 2 = -1, ceil(-1.5) = -1. -4 / 2 = -2, ceil(-2) = -2.
return a / b;
}
}
// Custom function for floor division: floor(a / b)
// Assumes b > 0
long long floor_div(long long a, long long b) {
// Standard C++ integer division truncates towards zero.
long long res = a / b;
// If a is negative and not perfectly divisible by b, standard division gives ceiling.
// Floor is one less in this case.
if (a < 0 && a % b != 0) {
res--;
}
return res;
}
int main() {
// Use fast IO
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N, M;
std::cin >> N >> M;
std::vector<int> L(N), R(N), X(N), Y(N);
int max_coord = 0; // Keep track of the maximum coordinate value seen
for (int i = 0; i < N; ++i) {
std::cin >> L[i] >> R[i] >> X[i] >> Y[i];
// Basic validation based on problem constraints
// L_i >= 1, R_i >= L_i, X_i >= 1, 0 <= Y_i < X_i
// We assume inputs adhere to constraints, but add minor guards if needed.
if (L[i] < 1) L[i] = 1; // Enforce L_i >= 1
if (R[i] < L[i]) R[i] = L[i]; // Enforce R_i >= L_i
if (X[i] < 1) X[i] = 1; // Enforce X_i >= 1
if (Y[i] < 0 || Y[i] >= X[i]) Y[i] = Y[i] % X[i]; // Ensure Y[i] is in [0, X[i]-1]
if (Y[i] < 0) Y[i] += X[i];
max_coord = std::max(max_coord, R[i]);
}
std::vector<int> A(M);
for (int j = 0; j < M; ++j) {
std::cin >> A[j];
// A_j >= 1
if (A[j] < 1) A[j] = 1; // Enforce A_j >= 1
max_coord = std::max(max_coord, A[j]);
}
int V = max_coord; // The maximum coordinate value determines the range needed
if (V == 0) V = 1; // Handle edge case where all coordinates are 0 (unlikely given constraints)
// Set the threshold B for splitting into "small X" and "large X" cases
// B = sqrt(V) is a common choice for balancing complexity
int B = static_cast<int>(sqrt(V));
if (B <= 0) B = 1; // Ensure B is at least 1
// Array to store counts contributed by conditions with large X_i (> B)
std::vector<int> count_large(V + 1, 0);
// Structure to group indices i based on (X_i, Y_i) pair for small X_i (<= B)
// groups[x][y] stores a list of indices i such that X_i = x and Y_i = y
std::vector<std::vector<std::vector<int>>> groups(B + 1);
for(int x_val = 1; x_val <= B; ++x_val) {
groups[x_val].resize(x_val); // Allocate inner vectors for Y values [0, x_val-1]
}
// Process each condition (L_i, R_i, X_i, Y_i)
for (int i = 0; i < N; ++i) {
if (X[i] == 0) continue; // Invalid X[i], skip (though constraints say X_i >= 1)
if (X[i] > B) { // Case 1: Large X_i
// Directly compute the values k satisfying the condition and update count_large
long long k_min;
int Li = L[i];
int Ri = R[i];
int Xi = X[i];
int Yi = Y[i];
// Calculate the smallest k >= Li such that k = Yi (mod Xi)
long long rem = (long long)Li % Xi; // Since Li >= 1, Xi >= 1, rem is in [0, Xi-1]
if (rem <= Yi) {
k_min = (long long)Li + (Yi - rem);
} else { // rem > Yi
k_min = (long long)Li + (Xi - rem) + Yi;
}
// If the smallest valid k is already outside the range [Li, Ri], skip
if (k_min > Ri) continue;
// Iterate through the arithmetic progression k = k_min, k_min + Xi, ...
for (long long k = k_min; k <= Ri; k += Xi) {
// Increment count only if k is within the valid coordinate range [1, V]
if (k >= 1 && k <= V) {
count_large[k]++;
} else if (k > V) { // Optimization: stop if k exceeds V
break;
}
}
} else { // Case 2: Small X_i (X_i <= B)
// Group the index i based on its (X_i, Y_i) pair
if (Y[i] >= 0 && Y[i] < X[i]) { // Ensure Y[i] is valid index
groups[X[i]][Y[i]].push_back(i);
}
}
}
// Precompute counts for small X cases using difference arrays / sweep line approach
// all_count_q[x][y][q] will store the number of conditions i with (X_i, Y_i) = (x, y)
// such that the value k = y + q*x satisfies L_i <= k <= R_i.
std::vector<std::vector<std::vector<int>>> all_count_q(B + 1);
for(int x_val = 1; x_val <= B; ++x_val) {
all_count_q[x_val].resize(x_val); // Allocate inner vectors
}
// Process each pair (X, Y) with X <= B
for (int X_val = 1; X_val <= B; ++X_val) {
for (int Y_val = 0; Y_val < X_val; ++Y_val) {
// Check if there are any conditions for this (X, Y) pair
if (!groups[X_val][Y_val].empty()) {
// Calculate the maximum possible index q such that Y_val + q * X_val <= V
long long Q_max_ll = floor_div((long long)V - Y_val, X_val);
// Check basic validity: if max q is negative, or results in k < 1
if (Q_max_ll < 0 || (Y_val == 0 && Q_max_ll < 1) ) continue;
int Q_max = static_cast<int>(Q_max_ll);
// Difference array for sweep line on q indices. Size Q_max + 2 for index Q_max + 1.
std::vector<int> diff(Q_max + 2, 0);
// Populate difference array based on q intervals for each condition i in the group
for (int i : groups[X_val][Y_val]) {
long long q_start, q_end;
// Calculate the interval [q_start, q_end] for index q
if (Y_val == 0) { // Special case Y=0: k = q*X. Need k >= L[i] and k >= 1.
q_start = ceil_div((long long)L[i], X_val);
q_start = std::max(1LL, q_start); // Ensure q >= 1 because k must be >= 1
q_end = floor_div((long long)R[i], X_val);
} else { // Case Y > 0: k = Y + q*X. Need k >= L[i]. k >= 1 is true for q >= 0.
q_start = ceil_div((long long)L[i] - Y_val, X_val);
q_start = std::max(0LL, q_start); // Ensure q >= 0
q_end = floor_div((long long)R[i] - Y_val, X_val);
}
// If the calculated interval is valid
if (q_start <= q_end) {
// Clamp the interval [q_start, q_end] to the valid range [0, Q_max]
q_start = std::max(q_start, 0LL);
q_end = std::min(q_end, (long long)Q_max);
// Apply updates to difference array if interval is still valid after clamping
if (q_start <= q_end) {
diff[q_start]++; // Increment count at start of interval
if (q_end + 1 <= Q_max + 1) { // Check bounds for difference array access
diff[q_end + 1]--; // Decrement count after end of interval
}
}
}
}
// Compute prefix sums of the difference array to get the actual counts for each q
all_count_q[X_val][Y_val].resize(Q_max + 1);
int current_count = 0;
for (int q = 0; q <= Q_max; ++q) {
current_count += diff[q];
all_count_q[X_val][Y_val][q] = current_count;
}
}
}
}
// Answer each query A_j
for (int j = 0; j < M; ++j) {
int Aj = A[j];
// Check if Aj is within the valid coordinate range [1, V]
if (Aj <= 0 || Aj > V) {
std::cout << 0 << "\n"; // Aj is outside the range, count must be 0
continue;
}
// Initialize total count with contribution from large X conditions
long long total_count = count_large[Aj];
// Add contributions from small X conditions
for (int X_val = 1; X_val <= B; ++X_val) {
// Determine the remainder Y_val corresponding to Aj for this X_val
int Y_val = Aj % X_val; // Y_val will be in [0, X_val-1] for positive Aj, X_val
// Check if this group (X_val, Y_val) has precomputed counts
if (Y_val < all_count_q[X_val].size() && !all_count_q[X_val][Y_val].empty()) {
// Calculate the index q corresponding to Aj: Aj = Y_val + qj * X_val
long long qj = (long long)(Aj - Y_val) / X_val; // Integer division is exact since Aj % X_val = Y_val
int Q_max_for_pair = all_count_q[X_val][Y_val].size() - 1;
// Check if qj is within the valid range [0, Q_max_for_pair] for this group
if (qj >= 0 && qj <= Q_max_for_pair) {
// Add the precomputed count for this qj
total_count += all_count_q[X_val][Y_val][qj];
}
}
}
// Output the final count for Aj
std::cout << total_count << "\n";
}
return 0;
}