結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:43:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,325 bytes
コンパイル時間 4,618 ms
コンパイル使用メモリ 207,580 KB
実行使用メモリ 23,312 KB
最終ジャッジ日時 2025-04-15 22:45:34
合計ジャッジ時間 27,544 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e18 + 9;

struct Interval {
    ll end;
    int team;
    ll thickness;
};

map<ll, Interval> intervals;

void split(ll x) {
    auto it = intervals.upper_bound(x);
    if (it != intervals.begin()) {
        --it;
        ll start = it->first;
        Interval current = it->second;
        if (current.end >= x) {
            intervals.erase(it);
            intervals[start] = {x - 1, current.team, current.thickness};
            intervals[x] = {current.end, current.team, current.thickness};
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll N;
    int Q;
    cin >> N >> Q;

    intervals[0] = {N - 1, 0, 0};

    vector<ll> bonus(6, 0);

    while (Q--) {
        int x;
        ll l, r;
        cin >> x >> l >> r;

        if (x == 0) { // Bonus query
            vector<ll> sum(6, 0);
            auto it = intervals.upper_bound(r);
            while (it != intervals.begin()) {
                --it;
                ll start = it->first;
                Interval current = it->second;
                if (current.end < l) break;

                ll overlap_start = max(start, l);
                ll overlap_end = min(current.end, r);
                if (overlap_start > overlap_end) continue;

                ll len = overlap_end - overlap_start + 1;
                if (current.team >= 1 && current.team <= 5) {
                    sum[current.team] += len * current.thickness;
                }
            }

            ll max_sum = 0;
            int count = 0;
            int max_team = -1;
            for (int i = 1; i <= 5; ++i) {
                if (sum[i] > max_sum) {
                    max_sum = sum[i];
                    count = 1;
                    max_team = i;
                } else if (sum[i] == max_sum) {
                    count++;
                }
            }
            if (count == 1) {
                bonus[max_team] = (bonus[max_team] + max_sum) % MOD;
            }
        } else { // Painting operation (team x)
            int team = x;
            split(l);
            split(r + 1);

            auto it_l = intervals.lower_bound(l);
            auto it_r = intervals.upper_bound(r);

            vector<pair<ll, Interval>> to_update;
            for (auto it = it_l; it != it_r;) {
                to_update.push_back({it->first, it->second});
                it = intervals.erase(it);
            }

            for (auto& [start, current] : to_update) {
                if (current.team == team) {
                    current.thickness++;
                } else {
                    current.team = team;
                    current.thickness = 1;
                }
                intervals[start] = current;
            }
        }
    }

    vector<ll> total(6, 0);
    for (auto& [start, current] : intervals) {
        if (current.team >= 1 && current.team <= 5) {
            ll len = current.end - start + 1;
            total[current.team] = (total[current.team] + len * current.thickness) % MOD;
        }
    }

    for (int i = 1; i <= 5; ++i) {
        total[i] = (total[i] + bonus[i]) % MOD;
    }

    cout << total[1] << " " << total[2] << " " << total[3] << " " << total[4] << " " << total[5] << endl;

    return 0;
}
0