結果
| 問題 |
No.1720 Division Permutation
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:57:06 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 10,712 bytes |
| コンパイル時間 | 1,459 ms |
| コンパイル使用メモリ | 105,836 KB |
| 実行使用メモリ | 813,528 KB |
| 最終ジャッジ日時 | 2025-05-14 12:59:07 |
| 合計ジャッジ時間 | 8,557 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 MLE * 1 -- * 44 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <functional> // for std::function
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int INF = 1e9 + 7; // Use a large value to represent infinity initially
// Structure for segment tree node
struct Node {
int min_val = INF; // Minimum value in the node's range
int count = 0; // Count of elements equal to min_val
ll lazy_add = 0; // Lazy tag for range additions
};
vector<Node> tree; // Segment tree
vector<int> p; // Input permutation P
vector<vector<int>> start_indices; // start_indices[e] stores list of start indices s such that P[s..e] is beautiful
// Build an empty segment tree initialized with large values
void build_empty(int node, int start, int end) {
tree[node] = {INF, 0, 0};
if (start == end) {
return;
}
int mid = start + (end - start) / 2;
build_empty(2 * node, start, mid);
build_empty(2 * node + 1, mid + 1, end);
}
// Push lazy tag down to children
void push(int node, int start, int end) {
if (tree[node].lazy_add == 0 || start == end) { // No lazy value or leaf node
if(start == end) tree[node].lazy_add = 0; // Clear lazy at leaf if needed
return;
}
// Apply lazy value to children's lazy tag
tree[2 * node].lazy_add += tree[node].lazy_add;
tree[2 * node + 1].lazy_add += tree[node].lazy_add;
// Clear lazy value of current node
tree[node].lazy_add = 0;
}
// Combine results from children into parent node
// This function computes the node's min_val and count based on children's effective values (considering their lazy tags)
void combine(int node, int start, int end) {
// Calculate effective minimum values of children
int left_min = tree[2 * node].min_val + tree[2 * node].lazy_add;
int right_min = tree[2 * node + 1].min_val + tree[2 * node + 1].lazy_add;
tree[node].min_val = min(left_min, right_min); // Parent's min is the minimum of children's effective mins
tree[node].count = 0;
if (tree[node].min_val == left_min) {
tree[node].count += tree[2*node].count;
}
if (tree[node].min_val == right_min) {
tree[node].count += tree[2*node+1].count;
}
}
// Update range [l, r] by adding add_val
void update_range(int node, int start, int end, int l, int r, int add_val) {
// Current node's effective minimum must be considered before range check logic.
// This calculation is implicit now because lazy tags are pushed down.
if (start > end || start > r || end < l) { // Out of range
return;
}
if (l <= start && end <= r) { // Fully contained range
tree[node].lazy_add += add_val; // Update lazy tag
return; // Don't recurse further, lazy tag handles the update
}
// Partially contained range: push lazy tag down and recurse
push(node, start, end); // Push lazy tag to children BEFORE recursing
int mid = start + (end - start) / 2;
update_range(2 * node, start, mid, l, r, add_val);
update_range(2 * node + 1, mid + 1, end, l, r, add_val);
// After updating children, recompute current node's value
combine(node, start, end);
}
// Update point idx to value val. Value `val` represents the target effective value V_idx.
// The base value stored in the leaf node needs to account for the lazy tag.
void update_point(int node, int start, int end, int idx, int val) {
push(node, start, end); // Push lazy tag down before processing
if (start == end) { // Leaf node
// Store base value such that base_value + lazy_add = val
tree[node].min_val = val - tree[node].lazy_add;
tree[node].count = 1;
return;
}
int mid = start + (end - start) / 2;
// Decide which child to recurse into
if (idx <= mid) {
update_point(2 * node, start, mid, idx, val);
} else {
update_point(2 * node + 1, mid + 1, end, idx, val);
}
// Recompute current node's value based on children
combine(node, start, end);
}
// Query range [l, r] for minimum value and count
pair<int, int> query_range(int node, int start, int end, int l, int r) {
if (start > end || start > r || end < l) { // Out of range
return {INF, 0}; // Return identity element
}
if (l <= start && end <= r) { // Fully contained range
// Return effective minimum value and count
return {tree[node].min_val + tree[node].lazy_add, tree[node].count};
}
// Partially contained range: push lazy tag down, query children and combine
push(node, start, end);
int mid = start + (end - start) / 2;
pair<int, int> p1 = query_range(2 * node, start, mid, l, r);
pair<int, int> p2 = query_range(2 * node + 1, mid + 1, end, l, r);
pair<int, int> res;
res.first = min(p1.first, p2.first);
res.second = 0;
if (res.first == p1.first) {
res.second += p1.second;
}
if (res.first == p2.first) {
res.second += p2.second;
}
return res;
}
vector<int> current_s; // Temporary storage for found indices s
// Recursive function to find all indices `s` in range `[l,r]` where the effective value V_s = 0
void find_zero_indices(int node, int start, int end, int l, int r, ll current_lazy_sum) {
// Calculate effective minimum for this node range considering accumulated lazy tags
ll accumulated_lazy = tree[node].lazy_add + current_lazy_sum;
int effective_min = tree[node].min_val + accumulated_lazy;
// Pruning: if node range is outside query range OR minimum value in node range is > 0, stop.
if (start > end || start > r || end < l || effective_min > 0) {
return;
}
if (start == end) {
// Leaf node within range and check its effective value
if (effective_min == 0) {
current_s.push_back(start);
}
return;
}
// Node range potentially contains 0s, recurse further
int mid = start + (end - start) / 2;
// Pass down the total accumulated lazy tag for children
find_zero_indices(2 * node, start, mid, l, r, accumulated_lazy);
find_zero_indices(2 * node + 1, mid + 1, end, l, r, accumulated_lazy);
}
int main() {
// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
long long K_ll; // Use long long for K for safety, though problem constraints say K is small
cin >> N >> K_ll;
int K = (int)K_ll; // K <= 10, fits in int
p.resize(N + 1);
for (int i = 1; i <= N; ++i) {
cin >> p[i];
}
// Initialize segment tree
tree.resize(4 * (N + 1));
build_empty(1, 1, N);
start_indices.resize(N + 1); // Adjacency list style storage for beautiful pairs (s, e)
vector<pair<int, int>> stack_max, stack_min; // Stacks for maintaining monotonic properties, store {value, index}
// Main loop iterating through end index `e`
for (int e = 1; e <= N; ++e) {
// Step 1: Account for incrementing `e`. This decreases V_s by 1 for all s < e.
// V_s = M_{s,e} - m_{s,e} + s - e
// When e -> e+1, the term `-e` becomes `-(e+1)`, so V_s decreases by 1.
if (e > 1) {
update_range(1, 1, N, 1, e - 1, -1);
}
// Step 2: Process the current element P[e]
int current_val = p[e];
// Update max stack and perform range updates on segment tree
while (!stack_max.empty() && stack_max.back().first <= current_val) {
pair<int, int> top = stack_max.back();
stack_max.pop_back();
int prev_idx = stack_max.empty() ? 0 : stack_max.back().second;
// Range [prev_idx + 1, top.second] now has max = current_val instead of top.first
// Change in V_s is (current_val - top.first) because M_{s,e} term increases.
if (prev_idx + 1 <= top.second)
update_range(1, 1, N, prev_idx + 1, top.second, current_val - top.first);
}
stack_max.push_back({current_val, e});
// Update min stack and perform range updates on segment tree
while (!stack_min.empty() && stack_min.back().first >= current_val) {
pair<int, int> top = stack_min.back();
stack_min.pop_back();
int prev_idx = stack_min.empty() ? 0 : stack_min.back().second;
// Range [prev_idx + 1, top.second] now has min = current_val instead of top.first
// Change in V_s is -(current_val - top.first) = top.first - current_val because -m_{s,e} term increases.
if (prev_idx + 1 <= top.second)
update_range(1, 1, N, prev_idx + 1, top.second, top.first - current_val);
}
stack_min.push_back({current_val, e});
// Step 3: Set V_e = M_{e,e} - m_{e,e} + e - e = 0. Update segment tree at index e.
update_point(1, 1, N, e, 0);
// Step 4: Query the segment tree for minimum value in range [1, e]. If minimum is 0, find all indices s.
pair<int, int> result = query_range(1, 1, N, 1, e);
if (result.first == 0) { // Check if minimum value is 0
current_s.clear(); // Clear temporary list
find_zero_indices(1, 1, N, 1, e, 0); // Find all indices s in [1,e] where V_s = 0
for (int s : current_s) {
start_indices[e].push_back(s); // Store the pair (s, e)
}
}
} // End of loop finding pairs (s, e)
// Dynamic Programming calculation
vector<vector<ll>> dp(N + 1, vector<ll>(K + 1, 0));
dp[0][0] = 1; // Base case: 0 elements partitioned into 0 subarrays is 1 way
// Iterate through indices i from 1 to N
for (int i = 1; i <= N; ++i) {
// If no beautiful subarrays end at i, dp[i] remains 0, can skip.
if (start_indices[i].empty()) continue;
// Iterate through all start indices `s` such that P[s..i] is beautiful
for (int s : start_indices[i]) {
int j = s - 1; // `j` is the end index of the previous subarray
if (j >= 0) { // Ensure j is valid index (0 to N-1)
// Iterate through possible number of subarrays `x` from 1 to K
for (int x = 1; x <= K; ++x) {
// Add ways to partition P[1..j] into x-1 subarrays
if (dp[j][x-1] > 0) { // Optimization: only add if there's a contribution
dp[i][x] = (dp[i][x] + dp[j][x-1]) % MOD;
}
}
}
}
}
// Output the results for X=1 to K
for (int x = 1; x <= K; ++x) {
cout << dp[N][x] << "\n";
}
return 0;
}