結果

問題 No.833 かっこいい電車
ユーザー kotatsugame
提出日時 2019-05-24 22:32:05
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 581 ms / 2,000 ms
コード長 1,729 bytes
コンパイル時間 1,339 ms
コンパイル使用メモリ 93,656 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-02 03:44:01
合計ジャッジ時間 7,554 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main()
      | ^~~~

ソースコード

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

#include<iostream>
#include<vector>
using namespace std;
#include<vector>
#include<functional>
#include<limits>
template<typename T>
struct segtree{
    function<T(T,T)>calcfn,updatefn;
    int n;
    T defvalue;
    vector<T>dat;
    segtree(int n_=0,T defvalue_=numeric_limits<T>::max(),
        function<T(T,T)>calcfn_=[](T a,T b){return a<b?a:b;},
        function<T(T,T)>updatefn_=[](T a,T b){return b;}
    ):defvalue(defvalue_),calcfn(calcfn_),updatefn(updatefn_)
    {
        n=1;
        while(n<n_)n<<=1;
        dat.assign(2*n-1,defvalue);
    }
    void copy(const vector<T>&v)
    {
        for(int i=0;i<v.size();i++)dat[i+n-1]=v[i];
        for(int i=n-2;i>=0;i--)dat[i]=calcfn(dat[i*2+1],dat[i*2+2]);
    }
    void update(int i,T a)
    {
        i+=n-1;
        dat[i]=updatefn(dat[i],a);
        while(i>0)
        {
            i=(i-1)/2;
            dat[i]=calcfn(dat[2*i+1],dat[2*i+2]);
        }
    }
    T query(int a,int b,int i=0,int l=0,int r=-1)//[a,b)
    {
        if(r<0)r=n;
        if(r<=a||b<=l)return defvalue;
        else if(a<=l&&r<=b)return dat[i];
        else
        {
            return calcfn(
                query(a,b,i*2+1,l,(l+r)/2),
                query(a,b,i*2+2,(l+r)/2,r)
            );
        }
    }
};
int N,q;
main()
{
    cin>>N>>q;
    segtree<long>P(N+1,0,[](long a,long b){return a+b;},[](long a,long b){return a+b;});
    segtree<bool>Q(N+1,true,[](bool a,bool b){return a&&b;});
    for(int i=0;i<N;i++)
    {
        long A;cin>>A;P.update(i+1,A);
    }
    for(int i=0;i<=N;i++)Q.update(i,false);
    for(;q--;)
    {
        int id,x;cin>>id>>x;
        if(id==1)Q.update(x,true);
        else if(id==2)Q.update(x,false);
        else if(id==3)P.update(x,1);
        else
        {
            int L,R,l,r;
            l=0,r=x;
            while(r-l>1)
            {
                int m=(r+l)/2;
                if(Q.query(m,x))r=m;
                else l=m;
            }
            L=r;
            l=x-1,r=N+1;
            while(r-l>1)
            {
                int m=(r+l)/2;
                if(Q.query(x,m))l=m;
                else r=m;
            }
            R=r;
            cout<<P.query(L,R)<<endl;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0