結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー latte0119latte0119
提出日時 2016-02-25 12:56:40
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2,260 ms / 10,000 ms
コード長 3,109 bytes
コンパイル時間 3,595 ms
コンパイル使用メモリ 160,436 KB
実行使用メモリ 155,844 KB
最終ジャッジ日時 2023-08-02 21:42:18
合計ジャッジ時間 24,809 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,084 ms
155,376 KB
testcase_01 AC 2,260 ms
155,712 KB
testcase_02 AC 2,013 ms
155,844 KB
testcase_03 AC 1,915 ms
155,416 KB
testcase_04 AC 59 ms
146,400 KB
testcase_05 AC 2,092 ms
155,036 KB
testcase_06 AC 1,941 ms
155,780 KB
testcase_07 AC 1,971 ms
155,232 KB
testcase_08 AC 1,980 ms
155,044 KB
testcase_09 AC 2,069 ms
154,684 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define int long long

typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ln <<endl
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

struct segtree{
    static const int SEG=1<<19;
    vint sum,put,zero;
    vint g;
    void init(vint _g){
        g.resize(SEG);rep(i,_g.size())g[i]=_g[i];
        sum.assign(SEG*2,0);
        put.assign(SEG*2,0);
        zero.assign(SEG*2,0);
    }
    inline void push(int k,int l,int r){
        if(zero[k])sum[k]=0;
        sum[k]+=(g[r]-g[l])*put[k];
        if(k<SEG-1){
            if(zero[k]){
                put[k*2+1]=put[k*2+2]=0;
                zero[k*2+1]=zero[k*2+2]=1;
            }
            put[k*2+1]+=put[k];
            put[k*2+2]+=put[k];
        }
        put[k]=0;zero[k]=0;
    }
    void add(int a,int b,int t,int k=0,int l=0,int r=SEG){
        push(k,l,r);
        if(r<=a||b<=l)return;
        if(a<=l&&r<=b){
            if(t)put[k]++;
            else zero[k]=1,put[k]=0;
            push(k,l,r);
            return;
        }
        add(a,b,t,k*2+1,l,(l+r)/2);
        add(a,b,t,k*2+2,(l+r)/2,r);
        sum[k]=sum[k*2+1]+sum[k*2+2];
    }
    int get(int a,int b,int k=0,int l=0,int r=SEG){
        push(k,l,r);
        if(r<=a||b<=l)return 0;
        if(a<=l&&r<=b)return sum[k];
        return get(a,b,k*2+1,l,(l+r)/2)+get(a,b,k*2+2,(l+r)/2,r);
    }
};

const int SIZE=150000;
int N,Q;
int x[SIZE],l[SIZE],r[SIZE];

segtree seg[5];
int ans[5];
const int mod=1000000000000000009ll;

signed main(){
    scanf("%lld%lld",&N,&Q);
    vint press;
    rep(i,Q){
        scanf("%lld%lld%lld",&x[i],&l[i],&r[i]),x[i]--,r[i]++;
        press.pb(l[i]);
        press.pb(r[i]);
    }
    sort(all(press));
    press.erase(unique(all(press)),press.end());

    rep(i,Q){
        l[i]=lower_bound(all(press),l[i])-press.begin();
        r[i]=lower_bound(all(press),r[i])-press.begin();
    }

    rep(i,5)seg[i].init(press);

    rep(i,Q){
        if(~x[i]){
            rep(j,5){
                if(j!=x[i])seg[j].add(l[i],r[i],0);
                else seg[j].add(l[i],r[i],1);
            }
        }
        else{
            int ma=-114,v=-1,f=1;
            rep(j,5){
                int tmp=seg[j].get(l[i],r[i]);
                if(ma<tmp){
                    ma=tmp;
                    v=j;
                    f=1;
                }
                else if(ma==tmp){
                    f=0;
                }
            }
            if(f){
                ans[v]=(ans[v]+ma)%mod;
            }
        }
    }

    rep(i,5)ans[i]=(ans[i]+seg[i].get(0,press.size()-1))%mod;
    rep(i,5){
        if(i)printf(" ");
        printf("%lld",ans[i]);
    }
    puts("");
    return 0;
}
0