結果

問題 No.674 n連勤
コンテスト
ユーザー vjudge1
提出日時 2025-10-19 16:04:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 2,452 bytes
コンパイル時間 1,675 ms
コンパイル使用メモリ 163,160 KB
実行使用メモリ 22,624 KB
最終ジャッジ日時 2025-10-19 16:04:36
合計ジャッジ時間 3,535 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define ls rt << 1
#define rs rt << 1 | 1
const int N = 5e5 + 7;
int op[N], l[N], r[N];
int tmp[N << 1], tot = 0;
struct node
{
    int ans, pre, suf, lazy, len;
} tr[N << 5];
inline node merge(node a, node b)
{
    node res;
    res.ans = res.len = res.pre = res.suf = res.lazy = 0;
    res.len = a.len + b.len;
    res.ans = max({a.ans, b.ans, a.suf + b.pre});
    if (a.pre == a.len)
        res.pre = a.len + b.pre;
    else
        res.pre = a.pre;
    if (b.suf == b.len)
        res.suf = b.len + a.suf;
    else
        res.suf = b.suf;
    return res;
}
inline void addlazy(int rt)
{
    tr[rt].lazy = 1;
    tr[rt].ans = tr[rt].len;
    tr[rt].pre = tr[rt].suf = tr[rt].len;
    return;
}
inline void pushdown(int rt)
{
    if (!rt)
        return;
    if (tr[rt].lazy)
    {
        addlazy(ls);
        addlazy(rs);
        tr[rt].lazy = 0;
    }
    return;
}
inline void build(int l, int r, int rt)
{
    tr[rt].lazy = 0;
    if (l == r)
    {
        if (l & 1)
        {
            tr[rt].len = 1;
        }
        else
        {
            tr[rt].len = tmp[l / 2 + 1] - tmp[l / 2] - 1;
        }
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, ls);
    build(mid + 1, r, rs);
    tr[rt].len = tr[ls].len + tr[rs].len;
    return;
}
inline void update(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        addlazy(rt);
        return;
    }

    int mid = (l + r) / 2;
    pushdown(rt);
    if (L <= mid)
        update(L, R, l, mid, ls);
    if (R > mid)
        update(L, R, mid + 1, r, rs);
    int p = tr[rt].lazy;
    tr[rt] = merge(tr[ls], tr[rs]);
    tr[rt].lazy = p;
    return;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // freopen("onduty.in", "r", stdin);
    // freopen("onduty.out", "w", stdout);

    int n, d;
    cin >> d >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> l[i] >> r[i];
        tmp[2 * i - 1] = l[i];
        tmp[2 * i] = r[i];
    }
    sort(tmp + 1, tmp + 1 + 2 * n);
    tot = unique(tmp + 1, tmp + 1 + 2 * n) - tmp - 1;
    build(1, 2 * tot - 1, 1);
    for (int i = 1; i <= n; i++)
    {
        l[i] = lower_bound(tmp + 1, tmp + 1 + tot, l[i]) - tmp;
        r[i] = lower_bound(tmp + 1, tmp + 1 + tot, r[i]) - tmp;
        update(l[i] * 2 - 1, r[i] * 2 - 1, 1, 2 * tot - 1, 1);
        cout << tr[1].ans << "\n";
    }
}
0