結果

問題 No.1888 Odd Insertion
ユーザー 👑 ygussany
提出日時 2022-03-10 19:22:12
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 363 ms / 2,000 ms
コード長 3,035 bytes
コンパイル時間 484 ms
コンパイル使用メモリ 33,664 KB
実行使用メモリ 16,768 KB
最終ジャッジ日時 2024-09-14 20:13:45
合計ジャッジ時間 17,448 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
void add_BIT(int N, int BIT[], int i, int k)
{
    while (i <= N) {
        BIT[i] += k;
        i += (i & -i);
    }
}
int sum_BIT(int BIT[], int r)
{
    int sum = 0;
    while (r > 0) {
        sum += BIT[r];
        r -= (r & -r);
    }
    return sum;
}
typedef struct {
    int left, right, max, la, lb;
} 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].max = 0;
    v[k].la = 3;
    v[k].lb = 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_max_to_root(lazy_seg_node v[], int k)
{
    int j;
    for (j = k >> 1; j > 0; k = j, j >>= 1) v[j].max = (v[k].max > v[k^1].max)? v[k].max: v[k^1].max;
}
void push_update_below(lazy_seg_node v[], int k)
{
    int j;
    if (v[k].left == v[k].right || (v[k].la == 3 && v[k].lb == 0)) return;
    j = k << 1;
    v[j].max = v[j].max & v[k].la ^ v[k].lb;
    v[j].la &= v[k].la;
    v[j].lb = v[j].lb & v[k].la ^ v[k].lb;
    j ^= 1;
    v[j].max = v[j].max & v[k].la ^ v[k].lb;
    v[j].la &= v[k].la;
    v[j].lb = v[j].lb & v[k].la ^ v[k].lb;
    v[k].la = 3;
    v[k].lb = 0;
}
void update_segment(lazy_seg_node v[], int k, int l, int r, int a, int b)
{
    if (r < v[k].left || v[k].right < l) return;
    else if (l <= v[k].left && v[k].right <= r) {
        v[k].max = v[k].max & a ^ b;
        v[k].la &= a;
        v[k].lb = v[k].lb & a ^ b;
        update_max_to_root(v, k);
    } else {
        push_update_below(v, k);
        update_segment(v, k << 1, l, r, a, b);
        update_segment(v, (k << 1) ^ 1, l, r, a, b);
    }
}
int BS_left(lazy_seg_node v[], int k, int l, int r, int x)
{
    int tmp;
    if (v[k].max < x || r < v[k].left || v[k].right < l) return r + 1;
    else if (v[k].left == v[k].right) return v[k].left;
    else {
        push_update_below(v, k);
        tmp = BS_left(v, k << 1, l, r, x);
        if (tmp <= r) return tmp;
        else return BS_left(v, (k << 1) ^ 1, l, r, x);
    }
}
int main()
{
    int i, N, P[200001], P_inv[200001];
    scanf("%d", &N);
    for (i = 1; i <= N; i++) scanf("%d", &(P[i]));
    for (i = 1; i <= N; i++) P_inv[P[i]] = i;
    
    int j, k, l, BIT[200001] = {}, start[200001] = {};
    lazy_seg_node v[524288];
    init_node(v, 1, 1, N);
    for (i = 1; i <= N; i++) {
        j = P_inv[i];
        k = sum_BIT(BIT, j - 1);
        add_BIT(N, BIT, j, 1);
        update_segment(v, 1, j, N, 3, 1);
        if (k % 2 == 0) {
            if (i == 1 || start[i-1] > 0) start[i] = i;
            update_segment(v, 1, 1, j - 1, 1, 0);
        } else update_segment(v, 1, j + 1, N, 1, 0);
        if (start[i] == 0) {
            l = BS_left(v, 1, 1, N, 3);
            if (l <= N) start[i] = P[l];
        }
        if (i == 1 || start[i-1] > 0) update_segment(v, 1, j, j, 3, 2);
    }
    if (start[N] == 0) {
        printf("No\n");
        fflush(stdout);
        return 0;
    }
    
    int ans[200001][2];
    for (i = N, k = N; i >= 1; i--) {
        j = start[i];
        ans[k][0] = j;
        ans[k--][1] = sum_BIT(BIT, P_inv[j]);
        add_BIT(N, BIT, P_inv[j], -1);
        for (; i > j; i--) {
            ans[k][0] = i;
            ans[k--][1] = sum_BIT(BIT, P_inv[i]);
            add_BIT(N, BIT, P_inv[i], -1);
        }
    }
    printf("Yes\n");
    for (i = 1; i <= N; i++) printf("%d %d\n", ans[i][0], ans[i][1]);
    fflush(stdout);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0