結果
問題 | No.759 悪くない忘年会にしような! |
ユーザー |
![]() |
提出日時 | 2019-06-07 02:09:42 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 1,487 bytes |
コンパイル時間 | 780 ms |
コンパイル使用メモリ | 30,336 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-02 08:45:31 |
合計ジャッジ時間 | 4,742 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 64 |
ソースコード
#include<stdio.h>#include<stdlib.h>#include<stdint.h>#include<inttypes.h>typedef int32_t i32;typedef struct node {i32 a, b, c;i32 index;} node;int cmp_node (const void *a, const void *b) {const node *p = a;const node *q = b;i32 d = p->a - q->a;if (d != 0) return d > 0 ? -1 : 1;d = p->b - q->b;if (d != 0) return d > 0 ? -1 : 1;d = p->c - q->c;return d > 0 ? -1 : 1;}i32 max (i32 a, i32 b) {return a > b ? a : b;}void update (i32 *bit, i32 x, i32 v) {i32 n = bit[0];for (i32 i = x; i <= n; i += i & -i) {bit[i] = max (bit[i], v);}}i32 find (i32 *bit, i32 x) {i32 res = 0;for (i32 i = x; i > 0; i -= i & -i) {res = max (res, bit[i]);}return res;}void run (void) {i32 n;scanf ("%" SCNi32, &n);node *p = (node *) calloc (n, sizeof (node));for (i32 i = 0; i < n; ++i) {i32 a, b, c;scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32, &a, &b, &c);a++; b++; c++;p[i] = (node) {a, b, c, i};}qsort (p, n, sizeof (node), cmp_node);uint8_t *ok = (uint8_t *) calloc (n, sizeof (uint8_t));const i32 m = 10000 + 1;i32 *bit = (i32 *) calloc (m + 1, sizeof (i32));bit[0] = m;for (i32 i = 0; i < n; ++i) {i32 k = m + 1 - p[i].b;if (find (bit, k) >= p[i].c) continue;ok[p[i].index] = 1;update (bit, k, p[i].c);}for (i32 i = 0; i < n; ++i) {if (ok[i]) {printf ("%" PRIi32 "\n", i + 1);}}}int main (void) {run();return 0;}