結果
| 問題 | No.1720 Division Permutation |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2021-10-16 15:59:31 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 297 ms / 4,000 ms |
| コード長 | 5,937 bytes |
| コンパイル時間 | 455 ms |
| コンパイル使用メモリ | 37,208 KB |
| 実行使用メモリ | 66,836 KB |
| 最終ジャッジ日時 | 2024-09-23 03:53:46 |
| 合計ジャッジ時間 | 11,799 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 60 |
ソースコード
#include <stdio.h>#include <stdlib.h>const int Mod = 998244353;typedef struct {int left, right, min, lc;} lazy_seg_node;void init_node(lazy_seg_node v[], int k, int l, int r){v[k].left = l;v[k].right = r;v[k].min = 0;v[k].lc = 0;if (l < r) {init_node(v, k << 1, l, (l + r) / 2);init_node(v, (k << 1) ^ 1, (l + r) / 2 + 1, r);}}void update_segment(lazy_seg_node v[], int k, int l, int r, int c){int i, j;if (v[k].left > r || v[k].right < l) return;else if (v[k].left >= l && v[k].right <= r) {v[k].lc += c;v[k].min += c;for (j = k, i = j >> 1; i > 0; j = i, i >>= 1) v[i].min = (v[j].min < v[j^1].min)? v[j].min: v[j^1].min;} else {if (v[k].lc != 0) {j = k << 1;v[j].min += v[k].lc;v[j^1].min += v[k].lc;v[j].lc += v[k].lc;v[j^1].lc += v[k].lc;v[k].lc = 0;}update_segment(v, k << 1, l, r, c);update_segment(v, (k << 1) ^ 1, l, r, c);}}int get_min(lazy_seg_node v[], int k, int l, int r){int tmp[2];if (k == 1) update_segment(v, 1, l, r, 0);if (v[k].left > r || v[k].right < l) return 100;else if (v[k].left >= l && v[k].right <= r) return v[k].min;else {tmp[0] = get_min(v, k << 1, l, r);tmp[1] = get_min(v, (k << 1) ^ 1, l, r);return (tmp[0] < tmp[1])? tmp[0]: tmp[1];}}int BS_right(lazy_seg_node v[], int k, int l, int r){int j, tmp;if (v[k].lc != 0) {j = k << 1;v[j].min += v[k].lc;v[j^1].min += v[k].lc;v[j].lc += v[k].lc;v[j^1].lc += v[k].lc;v[k].lc = 0;}if (v[k].min > 0 || v[k].right < l || v[k].left > r) return l - 1;else if (v[k].left == v[k].right) return v[k].left;else {tmp = BS_right(v, (k << 1) ^ 1, l, r);if (tmp >= l) return tmp;else return BS_right(v, k << 1, l, r);}}typedef struct {int x, y;} s_data;typedef struct {s_data d[200001];int size;} stack;void push(stack* s, s_data z){s->d[++(s->size)] = z;}s_data pop(stack* s){return s->d[(s->size)--];}typedef struct {int key, id;} data;void merge_sort(int n, data x[]){static data y[200001] = {};if (n <= 1) return;merge_sort(n / 2, &(x[0]));merge_sort((n + 1) / 2, &(x[n/2]));int i, p, q;for (i = 0, p = 0, q = n / 2; i < n; i++) {if (p >= n / 2) y[i] = x[q++];else if (q >= n) y[i] = x[p++];else y[i] = (x[p].key < x[q].key)? x[p++]: x[q++];}for (i = 0; i < n; i++) x[i] = y[i];}int main(){int i, N, K, P[200001];scanf("%d %d", &N, &K);for (i = 1; i <= N; i++) scanf("%d", &(P[i]));s_data d;stack s_seg, s_min, s_max;s_seg.size = 0;s_min.size = 0;s_max.size = 0;d.x = 1; // node named.y = 1; // left boundarypush(&s_seg, d);d.x = P[1]; // valued.y = 1; // left boundarypush(&s_min, d);push(&s_max, d);int j, k, u, n = N, par[400001], type[400001] = {}, left[400001];lazy_seg_node v[524288];init_node(v, 1, 1, N);for (u = 1; u <= N; u++) left[u] = u;for (i = 2; i <= N; i++) {j = i;while (s_min.size > 0) {d = pop(&s_min);if (d.x < P[i]) {push(&s_min, d);break;}update_segment(v, 1, d.y, j - 1, d.x - P[i]);j = d.y;}d.x = P[i];d.y = j;push(&s_min, d);j = i;while (s_max.size > 0) {d = pop(&s_max);if (d.x > P[i]) {push(&s_max, d);break;}update_segment(v, 1, d.y, j - 1, P[i] - d.x);j = d.y;}d.x = P[i];d.y = j;push(&s_max, d);update_segment(v, 1, 1, i - 1, -1);u = i;k = i;while (k > 1 && s_seg.size > 0) {j = BS_right(v, 1, 1, k - 1);if (j == 0) break;d = pop(&s_seg);if (j > d.y) {par[u] = d.x;u = par[u];k = d.y;continue;}par[u] = ++n;par[d.x] = n;left[n] = j;u = n;k = j;if (j == d.y) continue;type[n] = 1;while (d.y != j) {d = pop(&s_seg);par[d.x] = n;}}d.x = u;d.y = k;push(&s_seg, d);}int l[400001] = {}, w, r, deg[2][400001] = {}, q[400001], head, tail = 0, cur, prev;long long dp[400001][11] = {}, tmp[2][2][11];data *child[400001];for (u = 1; u <= n; u++) {if (par[u] != 0) deg[0][par[u]]++;else r = u;}for (u = 1; u <= n; u++) {if (deg[0][u] == 0) q[tail++] = u;else {child[u] = (data*)malloc(sizeof(data) * (deg[0][u] + 1));deg[1][u] = deg[0][u];}}for (u = 1; u <= n; u++) {if (u != r) {child[par[u]][l[par[u]]].key = left[u];child[par[u]][l[par[u]]++].id = u;}}for (head = 0; head < tail; head++) {u = q[head];if (deg[0][u] == 0) dp[u][1] = 1;else if (type[u] == 0) {merge_sort(deg[0][u], child[u]);for (j = 1, tmp[0][0][0] = 1, tmp[0][1][0] = 0; j <= K; j++) {tmp[0][0][j] = 0;tmp[0][1][j] = 0;}for (i = 0, cur = 1, prev = 0; i < deg[0][u]; i++, cur ^= 1, prev ^= 1) {w = child[u][i].id;for (j = 0; j <= K; j++) {tmp[cur][0][j] = 0;tmp[cur][1][j] = 0;}for (j = 0; j <= K; j++) {for (k = 1; j + k <= K; k++) tmp[cur][0][j+k] += tmp[prev][0][j] * dp[w][k] % Mod;tmp[cur][1][j] += tmp[prev][0][j] + tmp[prev][1][j];if (j < K) tmp[cur][0][j+1] += tmp[prev][1][j];}for (j = 0; j <= K; j++) {tmp[cur][0][j] %= Mod;tmp[cur][1][j] %= Mod;}}for (j = 1; j <= K; j++) dp[u][j] = tmp[prev][0][j];} else {for (i = 0, dp[u][0] = 1; i < deg[0][u]; i++) {w = child[u][i].id;for (j = K; j >= 0; j--) {for (k = j, dp[u][j] = 0; k > 0; k--) dp[u][j] += dp[u][j-k] * dp[w][k] % Mod;dp[u][j] %= Mod;}}dp[u][1]++;}if (u == r) continue;deg[1][par[u]]--;if (deg[1][par[u]] == 0) q[tail++] = par[u];}for (i = 1; i <= K; i++) printf("%lld\n", dp[r][i]);fflush(stdout);return 0;}