結果
| 問題 |
No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:09:16 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 294 ms / 6,000 ms |
| コード長 | 8,715 bytes |
| コンパイル時間 | 1,069 ms |
| コンパイル使用メモリ | 83,844 KB |
| 実行使用メモリ | 55,500 KB |
| 最終ジャッジ日時 | 2025-05-14 13:10:43 |
| 合計ジャッジ時間 | 19,173 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 42 |
ソースコード
#include <vector> // For std::vector
#include <iostream> // For input/output streams (cin, cout)
#include <algorithm> // For std::sort
#include <vector> // Included again, typically not needed but harmless
// Using namespace std globally is common in competitive programming
// but generally avoided in larger projects to prevent name collisions.
using namespace std;
// Define long long type alias for convenience, used for large sums.
typedef long long ll;
// Fenwick tree structure (Binary Indexed Tree)
// Supports point updates and prefix sum queries in O(log N) time.
struct FenwickTree {
vector<ll> tree; // Stores the Fenwick tree data using long long for potentially large sums
int size; // Size of the array the Fenwick tree represents
// Constructor initializes the tree of size n.
// Uses n+1 storage for 1-based indexing convenience.
FenwickTree(int n) : size(n) {
tree.assign(n + 1, 0); // Initialize tree elements to 0
}
// Adds delta to the element at index idx (1-based).
// Updates the tree structure accordingly.
void update(int idx, ll delta) {
// Check for invalid index (must be within 1 to size)
if (idx <= 0 || idx > size) return;
// Traverse up the tree structure, updating relevant nodes
for (; idx <= size; idx += idx & -idx) { // idx & -idx gives the lowest set bit
tree[idx] += delta;
}
}
// Queries the prefix sum up to index idx (1-based).
// Returns the sum of elements from index 1 to idx.
ll query(int idx) {
// Handle edge cases: index out of bounds
if (idx <= 0) return 0; // Query up to 0 or negative index is 0
if (idx > size) idx = size; // Cap index if it exceeds tree size
ll sum = 0;
// Traverse down the tree structure, summing relevant nodes
for (; idx > 0; idx -= idx & -idx) {
sum += tree[idx];
}
return sum;
}
// Queries the sum of elements in the range [L, R] (1-based).
// Calculated as prefix_sum(R) - prefix_sum(L-1).
ll query_range(int L, int R) {
if (L > R) return 0; // Handle empty or invalid range
// query(L-1) correctly handles L=1 because query(0) returns 0.
return query(R) - query(L - 1);
}
};
// Structure to represent events (queries or state transitions)
// Used for the sweep-line algorithm approach.
struct Event {
int time; // Time at which the event occurs (D for query, T_i or Z_i for transition)
int type; // Event type: 0 for query, 1 for transition 1->2a/2b, 2 for transition 2a->2b
int idx; // Index 'i' of the element involved in a transition event
int L, R; // Range [L, R] for a query event
int query_idx; // Original index of the query (to store the result correctly)
ll valA; // Initial value A[i] needed for transition type 1
ll valY; // Value Y_i = A[i] + T[i] - 1 needed for transitions
// Custom comparison operator for sorting events.
// Primary sort key is time.
// Secondary sort key is type, ensuring transitions are processed before queries at the same time.
bool operator<(const Event& other) const {
if (time != other.time) {
return time < other.time; // Sort by time ascending
}
// If times are equal, process transitions (types 1, 2) before queries (type 0).
// Higher type number indicates a transition, so sort types descending (2 > 1 > 0).
return type > other.type;
}
};
int main() {
// Optimize standard I/O operations for speed
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of elements in the sequence
cin >> N;
// Use vectors of size N+1 for 1-based indexing consistency with Fenwick trees
vector<ll> A(N + 1);
vector<ll> T(N + 1);
vector<Event> events; // Vector to store all events
// Initialize three Fenwick trees:
FenwickTree ft1(N); // Stores sum of A_i for elements currently in state 1
FenwickTree ft2a_Y(N); // Stores sum of Y_i = A_i + T_i - 1 for elements in state 2a
FenwickTree ft2a_count(N); // Stores count (1 per element) of elements in state 2a
// Read input for each element, initialize state, and create transition events
for (int i = 1; i <= N; ++i) {
cin >> A[i] >> T[i];
// Calculate Y_i and Z_i using long long to prevent potential overflow issues.
ll Yi = A[i] + T[i] - 1;
ll Zi_ll = A[i] + T[i];
// The problem constraints state T_i >= 1.
// Time points T_i and Z_i can be up to 2*10^9, fitting safely within a standard 32-bit signed int.
int Ti_int = (int)T[i];
int Zi_int = (int)Zi_ll;
// Initialize FT1: At time D=0, all elements are in state 1. Add their initial A[i] value.
ft1.update(i, A[i]);
// Create the first transition event for element i: state 1 -> 2a/2b.
// This happens at time T_i. We pass A[i] and Y[i] needed for the update logic.
events.push_back({Ti_int, 1, i, 0, 0, -1, A[i], Yi});
// Create the second transition event for element i: state 2a -> 2b.
// This happens at time Z_i = A_i + T_i.
// This transition only happens if the element enters state 2a, which requires A[i] > 0.
if (A[i] > 0) {
// Pass Y[i] needed for removal from state 2a contribution.
events.push_back({Zi_int, 2, i, 0, 0, -1, 0, Yi});
}
}
int Q; // Number of queries
cin >> Q;
vector<ll> results(Q); // Vector to store the answer for each query
// Read queries and add them as events
for (int q = 0; q < Q; ++q) {
int D; // Query day D
int L, R; // Query range [L, R]
cin >> D >> L >> R;
// Problem states D_q >= 0.
events.push_back({D, 0, 0, L, R, q, 0, 0}); // Type 0 for query events
}
// Sort all events based on time, then type (transitions before queries)
sort(events.begin(), events.end());
// Process events in sorted order using the sweep-line approach
for (const auto& ev : events) {
if (ev.type == 0) { // Process query event
int D = ev.time; // Current time for the query
int L = ev.L; // Left boundary of query range
int R = ev.R; // Right boundary of query range
int q_idx = ev.query_idx; // Original index of this query
// Query the Fenwick trees to get necessary sums and counts for the range [L, R]
ll sum1 = ft1.query_range(L, R); // Sum of A_i for elements in state 1
ll sum2a_Y = ft2a_Y.query_range(L, R); // Sum of Y_i for elements in state 2a
ll count2a = ft2a_count.query_range(L, R); // Count of elements in state 2a
// Calculate the final answer using the derived formula: Sum = Sum1 + Sum2a_Y - D * Count2a
// Use long long for the multiplication D * Count2a to prevent overflow.
results[q_idx] = sum1 + sum2a_Y - (ll)D * count2a;
} else if (ev.type == 1) { // Process transition event: 1 -> 2a/2b
int i = ev.idx; // Index of the element transitioning
ll Ai = ev.valA; // Initial value A[i]
ll Yi = ev.valY; // Value Y[i] = A[i] + T[i] - 1
// Element leaves state 1. Remove its contribution A[i] from FT1.
ft1.update(i, -Ai);
// Check if element moves to state 2a or directly to 2b.
if (Ai > 0) {
// If A[i] > 0, element moves to state 2a.
// Add its contribution to FT2a_Y and FT2a_count.
ft2a_Y.update(i, Yi);
ft2a_count.update(i, 1);
}
// If Ai == 0, element moves directly from state 1 to state 2b.
// State 2b has 0 contribution, so no updates needed for FT2a trees.
} else { // Process transition event: 2a -> 2b (ev.type == 2)
int i = ev.idx; // Index of the element transitioning
ll Yi = ev.valY; // Value Y[i] = A[i] + T[i] - 1
// This event only occurs if A[i] > 0 initially.
// Element leaves state 2a and moves to state 2b.
// Remove its contribution from FT2a_Y and FT2a_count.
ft2a_Y.update(i, -Yi);
ft2a_count.update(i, -1);
}
}
// Output the results for all queries, each on a new line.
for (int q = 0; q < Q; ++q) {
cout << results[q] << "\n";
}
return 0; // Indicate successful execution
}