結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー hourenhouren
提出日時 2022-09-15 16:18:38
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,893 bytes
コンパイル時間 2,393 ms
コンパイル使用メモリ 191,032 KB
実行使用メモリ 167,336 KB
最終ジャッジ日時 2024-05-09 17:39:30
合計ジャッジ時間 17,406 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 1,380 ms
167,056 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/lazysegtree>
using namespace atcoder;
using ll = long long;
using P = pair<ll,ll>;
#define fix(x) fixed << setprecision(x)
#define asc(x) x, vector<x>, greater<x>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define all(x) (x).begin(),(x).end()
template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;}
const ll MOD = (ll)(1e18)+9;
struct S{
    ll val, siz;
};
using F = ll;
const F ID = 0;
S op(S a, S b){ return {a.val+b.val, a.siz+b.siz}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){
    return (f>=0 ? (S){x.val + f*x.siz, x.siz} : (S){0, x.siz});
}
F composition(F f, F g){
    return (f>=0 ? f + g : -1);
}
F id(){ return ID; }
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n,q;
    cin >> n >> q;
    set<ll> se;
    vector<ll> x(q), l(q), r(q);
    rep(i,q){
        cin >> x[i] >> l[i] >> r[i];
        x[i]--; r[i]++;
        se.insert(l[i]);
        se.insert(r[i]);
    }
    map<ll, ll> mp;
    vector<S> vec;
    ll now = 0, pre = -1;
    for(ll y:se){
        if(pre>=0) vec.push_back({0,y-pre});
        pre = y;
        mp[y] = now++;
    }
    vector<ll> ans(5,0);
    vector<lazy_segtree<S, op, e, F, mapping, composition, id>> seg(5,lazy_segtree<S, op, e, F, mapping, composition, id>(vec));
    rep(i,q){
        if(x[i]<0){
            ll t = -1, p = -1;
            rep(j,5){
                ll k = seg[j].prod(mp[l[i]], mp[r[i]]).val;
                if(chmax(p, k)) t = j;
                else if(p==k) t = -1;
            }
            if(t>=0) ans[t] = (ans[t] + p) % MOD;
        }else{
            rep(j,5) seg[j].apply(mp[l[i]], mp[r[i]], (x[i]==j)*2-1);
        }
    }
    rep(i,5) cout << (ans[i] + seg[i].all_prod().val) % MOD << " ";
    cout << '\n';
    return 0;
}
0