محدودیت زمان: ۳ ثانیه محدودیت حافظه: ۲۵۶ مگابایت آقای مهندس و خانم دکتر تصمیم گرفتهاند…
- User
محدودیت زمان: ۳ ثانیه محدودیت حافظه: ۲۵۶ مگابایت آقای مهندس و خانم دکتر تصمیم گرفتهاند تابستان را به طور کامل استراحت کنند و برای مدتی کار را کنار بگذارند. آنها روستای پدری آقای مهندس را برای استراحت انتخاب کردهاند. هر دوی آنها به کشاورزی علاقهمند هستند و قصد دارند در مدت تعطیلات، در زمین زراعی که متعلق به پدر آقای مهندس است، کشاورزی کنند. ولی در نوع محصول بایکدیگر به توافق نرسیدهاند! آقای مهندس دوست دارد توتفرنگی بکارد، ولی خانم دکتر کاشتن شلغم را ترجیح میدهد. برای همین آنها تصمیم گرفتهاند زمین را قسمتبندی کنند.
زمین زراعی را میتوان به صورت یک مستطیل h × w h×w در نظر گرفت. آنها قرار است با استفاده از جوبهای افقی و عمودی، قسمتبندی را انجام دهند و در هر کدام از قسمتها شلغم یا توتفرنگی بکارند. برای اینکه زمین کشاورزی خوشگل شود، آنها به این نتیجه میرسند که محصولات را به صورت شطرنجی بکارند. یعنی محصول هیچ دو قسمتی که مرز مشترک دارند، (یک نقطه به تنهایی مرز مشترک محسوب نمیشود) یکی نباشد. جوبکشی با آقای مهندس است و انتخاب اینکه محصولات به چه صورت کاشته شوند، با خانم دکتر است. (دقت کنید که تنها دو حالت وجود دارد) خانم دکتر هم که از شلغم بیشتر خوشش میآید، دوست دارد نحوه کاشتن محصولات را طوری تعیین کند که مقدار شلغمی که باید کاشته شود، بیشینه شود.
شما باید برنامهای بنویسید که با گرفتن اطلاعات مربوط به جوبکشیهای آقای مهندس بر حسب زمان، بعد از هر جوبی که ایجاد میشود، مشخص کند خانم دکتر چه مقدار از زمین را به کاشتن شلغم اختصاص میدهد.
توضیح تصویر
«ورودی نمونه اول مانند تصویر سوال است»
ورودی سطر اول ورودی به ترتیب شامل سه عدد طبیعی w w، عرض زمین، h h، طول زمین و q q، تعداد جوبکشیها، آمده است.
در هر کدام از q q سطر بعدی، ابتدا
t ∈ H , V t∈H,V
و سپس عدد p p میآید که کشیده شدن یک جوب را نشان میدهد. در صورتی که t t برابر با H H باشد یک جوب افقی در راستای y
p ( 0 < p < h ) y=p(0<p<h) کشیده میشود و در صورتی که t t مساوی با V باشد، یک جوب عمودی در راستای x
p ( 0 < p < w ) x=p(0<p<w) کشیده میشود.
تضمین میشود که هیچ دو جوبی در یک راستا کشیده نمیشوند.
1 ≤ w , h ≤ 1 0 9 1≤w,h≤10 9
1 ≤ q ≤ 500
000 1≤q≤500 000
خروجی خروجی شامل q q سطر است که در سطر i iام از آن مقدار مساحتی از زمین را که با در نظر گرفتن i i جوب اول باید در آن شلغم کاشته شود، چاپ کنید.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۵ q ≤ 500 q≤500 ۲ ۵ تمام جوبها در یک جهت هستند(همه افقی یا عمودی هستند) , q ≤ 5
000 q≤5 000 ۳ ۲۵ q ≤ 5
000 q≤5 000 ۴ ۲۰ تمام جوبها در یک جهت هستند(همه افقی یا عمودی هستند) ۵ ۴۵ بدون محدودیت اضافی مثال ورودی نمونه ۱ 4 3 2 V 1 H 2 Plain text خروجی نمونه ۱ 9 7 Plain text ورودی نمونه ۲ 5 5 4 H 3 H 2 H 4 H 1 Plain text خروجی نمونه ۲ 15 20 15 15 c++
- Assistant
To solve this problem efficiently, we need to manage dynamic partitions of a large rectangular field while maintaining optimal assignments in a checkerboard pattern to maximize the area allocated to shalgham. Given the constraints, an efficient data structure like an Implicit Treap (a type of balanced binary search tree) is appropriate to handle dynamic insertions and range-based queries efficiently.
Approach Overview
-
Data Structures:
- Horizontal and Vertical Cuts: We will maintain two separate treaps: one for horizontal cuts and another for vertical cuts. Each treap will represent the current partitioning of the field in that direction.
- Treap Node: Each node in the treap will represent a segment (a row or a column) with attributes:
length: The length of the segment.priority: A randomly assigned value to maintain the treap's balance.size: The size of the subtree rooted at this node.sum_oddandsum_even: The sum of lengths at odd and even indices within the subtree.flip: A flag to indicate if the parity of indices in the subtree needs to be flipped (used during insertions).
-
Key Operations:
- Split: Divides a treap into two based on a given position.
- Merge: Combines two treaps into one while maintaining the treap properties.
- Insert: Inserts a new segment into the treap, adjusting the sums accordingly.
- Flip Parity: When a new cut is inserted, it might change the parity (odd/even) of the segments that follow. This operation efficiently handles such parity flips.
-
Algorithm Steps:
- Initialization: Start with the entire field as a single segment in both horizontal and vertical treaps.
- Processing Cuts:
- For each cut (either horizontal
Hor verticalV), determine where to insert the new line. - Update the corresponding treap by splitting the existing segment at the cut position, inserting the two new segments, and flipping the parity of subsequent segments.
- For each cut (either horizontal
- Calculating Maximum Shalgham Area:
- After each cut, calculate the sum of lengths at odd and even indices for both horizontal and vertical treaps.
- Use these sums to compute two possible allocations (
sum(S)andsum(T)) corresponding to the two checkerboard patterns. - Choose the maximum of these two allocations as the optimal shalgham area.
-
Complexity:
- Each insertion and query operation on the treap takes (O(\log q)) time on average, where (q) is the number of cuts. Given the constraints ((q \leq 500,000)), this approach is efficient enough.
C++ Implementation
Below is the C++ implementation of the described approach. This code uses an implicit treap to manage dynamic insertions and efficiently calculate the required sums after each cut.
#include <bits/stdc++.h> using namespace std; // Treap Node definition struct Node { long long length; int priority; Node* left; Node* right; int size; long long sum_odd; long long sum_even; bool flip; Node(long long len) : length(len), priority(rand()), left(nullptr), right(nullptr), size(1), sum_odd(len), sum_even(0), flip(false) {} }; // Update function to maintain size and sum_odd/sum_even void update(Node* t) { if (!t) return; t->size = 1; t->sum_odd = t->length; t->sum_even = 0; if (t->left) { t->size += t->left->size; t->sum_odd += t->left->sum_odd; t->sum_even += t->left->sum_even; } if (t->right) { // If left size +1 is odd, right starts at even if ((t->left ? t->left->size : 0) +1 %2 ==1){ t->sum_odd += t->right->sum_even; t->sum_even += t->right->sum_odd; } else{ t->sum_odd += t->right->sum_odd; t->sum_even += t->right->sum_even; } t->size += t->right->size; } } // Push down the flip flag void push_down(Node* t) { if (t && t->flip) { swap(t->sum_odd, t->sum_even); if (t->left) t->left->flip ^= 1; if (t->right) t->right->flip ^= 1; t->flip = false; } } // Split treap into left with first k nodes and right with rest void split(Node* t, int k, Node*& left, Node*& right) { if (!t) { left = right = nullptr; return; } push_down(t); int left_size = t->left ? t->left->size : 0; if (k <= left_size) { split(t->left, k, left, t->left); right = t; } else { split(t->right, k - left_size -1, t->right, right); left = t; } update(t); } // Merge two treaps Node* merge(Node* left, Node* right) { if (!left || !right) return left ? left : right; if (left->priority > right->priority) { push_down(left); left->right = merge(left->right, right); update(left); return left; } else { push_down(right); right->left = merge(left, right->left); update(right); return right; } } // Insert two new lengths at position k Node* insert(Node* t, int k, long long len1, long long len2) { Node* left; Node* right; split(t, k, left, right); Node* new_node1 = new Node(len1); Node* new_node2 = new Node(len2); Node* merged = merge(left, new_node1); merged = merge(merged, new_node2); // Flip the parity of the right treap if (right) { right->flip ^=1; } merged = merge(merged, right); return merged; } // Get sum_odd and sum_even pair<long long, long long> get_sums(Node* t){ if(!t) return {0,0}; return {t->sum_odd, t->sum_even}; } int main(){ ios::sync_with_stdio(false); cin.tie(0); srand(time(0)); long long w, h; int q; cin >> w >> h >> q; // Initialize horizontal and vertical treaps Node* horizontal = new Node(h); Node* vertical = new Node(w); // Maintain sorted sets of horizontal and vertical cuts set<long long> hor_cuts, ver_cuts; hor_cuts.insert(0); hor_cuts.insert(h); ver_cuts.insert(0); ver_cuts.insert(w); while(q--){ char type; long long p; cin >> type >> p; if(type == 'H'){ // Find where to insert auto it = hor_cuts.lower_bound(p); auto it_prev = it; it_prev--; long long prev = *it_prev; long long next = *it; hor_cuts.insert(p); // Find the index of the split // Count number of elements less than p int k = distance(hor_cuts.begin(), it_prev) ; // Calculate new lengths long long len1 = p - prev; long long len2 = next - p; // Update the treap horizontal = insert(horizontal, k, len1, len2); } else{ // V auto it = ver_cuts.lower_bound(p); auto it_prev = it; it_prev--; long long prev = *it_prev; long long next = *it; ver_cuts.insert(p); // Find the index of the split int k = distance(ver_cuts.begin(), it_prev); // Calculate new lengths long long len1 = p - prev; long long len2 = next - p; // Update the treap vertical = insert(vertical, k, len1, len2); } // Get sums pair<long long, long long> sum_h = get_sums(horizontal); pair<long long, long long> sum_v = get_sums(vertical); // Calculate sum(S) and sum(T) long long S = sum_h.first * sum_v.first + sum_h.second * sum_v.second; long long T = sum_h.first * sum_v.second + sum_h.second * sum_v.first; cout << max(S, T) << "\n"; } }Explanation of the Code:
-
Treap Implementation:
- Node Structure: Each treap node stores the length of a segment, its priority (for balancing), pointers to left and right children, the size of the subtree, sums of lengths at odd and even indices, and a flip flag.
- Update Function: Recalculates the
size,sum_odd, andsum_evenbased on the current structure of the treap. - Push Down Function: Handles the propagation of the flip flag to child nodes, ensuring that sums are correctly maintained when parity changes.
- Split and Merge Functions: Standard treap operations that allow us to insert and manage segments efficiently.
-
Handling Cuts:
- Insertion: For each cut, determine its position relative to existing cuts using a
set. Split the corresponding treap, insert new segments, and flip the parity of subsequent segments to maintain the checkerboard pattern. - Sum Calculation: After each insertion, retrieve the sums of lengths at odd and even indices for both horizontal and vertical treaps. Compute the two possible shalgham areas (
sum(S)andsum(T)) and output the maximum.
- Insertion: For each cut, determine its position relative to existing cuts using a
-
Efficiency Considerations:
- Balanced Treap: The treap ensures that all operations (insertion, split, merge) occur in (O(\log q)) time on average, making the solution efficient for up to 500,000 cuts.
- Lazy Propagation: The flip flags allow us to defer and batch parity updates, optimizing performance.
Conclusion
This solution effectively manages dynamic partitions and maintains the necessary sums to determine the optimal allocation of shalgham in real-time as new cuts are introduced. By leveraging an implicit treap with lazy propagation, the solution operates efficiently within the given constraints.
-