結果
問題 | No.2667 Constrained Permutation |
ユーザー | 👑 ygussany |
提出日時 | 2024-02-18 10:23:04 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 797 ms / 2,000 ms |
コード長 | 1,911 bytes |
コンパイル時間 | 423 ms |
コンパイル使用メモリ | 32,000 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-29 00:16:36 |
合計ジャッジ時間 | 11,945 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
#include <stdio.h>typedef struct {int key, id;} data;typedef struct {data obj[200001];int size;} min_heap;void push(min_heap* h, data x){int i = ++(h->size), j = i >> 1;data tmp;h->obj[i] = x;while (j > 0) {if (h->obj[i].key < h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;i = j;j >>= 1;} else break;}}data pop(min_heap* h){int i = 1, j = 2;data output = h->obj[1], tmp;h->obj[1] = h->obj[(h->size)--];while (j <= h->size) {if (j < h->size && h->obj[j^1].key < h->obj[j].key) j ^= 1;if (h->obj[j].key < h->obj[i].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;i = j;j <<= 1;} else break;}return output;}void chmin(int *a, int b){if (*a > b) *a = b;}void chmax(int *a, int b){if (*a < b) *a = b;}int main(){int i, n, l[200001], r[200001];scanf("%d", &n);for (i = 1; i <= n; i++) scanf("%d %d", &(l[i]), &(r[i]));int k, L = 0, R = 1000000000, M;min_heap h[2];data d;while (L <= R) {M = (L + R) / 2;h[0].size = 0;h[1].size = 0;for (i = 1; i <= n; i++) {d.key = l[i] - M;d.id = i;push(&(h[0]), d);}for (i = 1; i <= n; i++) {while (h[0].size > 0 && h[0].obj[1].key <= i) {d = pop(&(h[0]));d.key = r[d.id] - M;push(&(h[1]), d);}if (h[1].size == 0 || h[1].obj[1].key < i) break;pop(&(h[1]));}if (i <= n) {if (h[1].size == 0) L = M + 1;else R = M - 1;} else break;}if (L > R) {printf("0\n");return 0;}L = 0;R = 1000000000;h[0].size = 0;h[1].size = 0;for (i = 1; i <= n; i++) {d.key = l[i];d.id = i;push(&(h[0]), d);d.key = r[i];d.id = i;push(&(h[1]), d);}for (i = 1; i <= n; i++) {d = pop(&(h[0]));chmax(&L, d.key - i);d = pop(&(h[1]));chmin(&R, d.key - i);}printf("%d\n", R - L + 1);fflush(stdout);return 0;}