#38412 (C++11) No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ

提出ソース
結果

問題	No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー	LayCurse
提出日時	2015-07-23 13:54:21
言語	C++11 (gcc 11.4.0)
結果	RE
実行時間	-
コード長	8,967 bytes
コンパイル時間	1,676 ms
コンパイル使用メモリ	161,832 KB
実行使用メモリ	52,488 KB
最終ジャッジ日時	2023-09-22 21:37:27
合計ジャッジ時間	8,202 ms
ジャッジサーバーID （参考情報）	judge13 / judge15
このコードへのチャレンジ
（要ログイン）
テストケース

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

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}

template<class T, class S>
struct lazySegtreeSumWithCoef{
  int N, logN;
  T *data, *addval;
  T *fixval; char *fixed;
  S *coef, *coefsum;

  void malloc(int maxN){
    int i;
    for(i=1;i<maxN;i*=2);
    data=(T*)std::malloc(sizeof(T)*2*i);
    fixval=(T*)std::malloc(sizeof(T)*i);
    addval=(T*)std::malloc(sizeof(T)*i);
    fixed=(char*)std::malloc(sizeof(char)*i);
    coef=(S*)std::malloc(sizeof(T)*i);
    coefsum=(S*)std::malloc(sizeof(T)*(i+1));
  }
  
  void* malloc(int maxN, void *mem){
    int i;
    for(i=1;i<maxN;i*=2);
    data=(T*)mem;
    fixval=data+2*i;
    addval=fixval+i;
    fixed=(char*)(addval+i);
    coef=(S*)(fixed+i);
    coefsum=coef+i;
    return coefsum+i+1;
  }
  
  T& operator[](int i){return data[N+i];}
  
  void setN(int n, int zerofill=1){
    int i;
    for(i=1,logN=0;i<n;i*=2,logN++);
    N=i;
    if(zerofill){
      rep(i,N)data[N+i]=0;
      rep(i,N)coef[i]=0;
    }
  }
  
  void build(void){
    int i;
    for(i=N-1;i;i--)data[i]=data[2*i]+data[2*i+1];
    REP(i,1,N) fixed[i] = 0;
    REP(i,1,N) addval[i] = 0;
    coefsum[0]=0;
    rep(i,N)coefsum[i+1]=coefsum[i]+coef[i];
  }
  
  inline void push_one(int a, int st, int ed){
    if(fixed[a]){
      if(ed-st>2){
        fixed[a*2] = fixed[a*2+1] = 1;
        fixval[a*2] = fixval[a*2+1] = fixval[a];
      }
      data[a*2] = (coefsum[(st+ed)/2]-coefsum[st])*fixval[a];
      data[a*2+1] = (coefsum[ed]-coefsum[(st+ed)/2])*fixval[a];
      fixed[a] = 0;
      addval[a] = 0;
      return;
    }
    
    if(addval[a]!=0){
      if(ed-st>2){
        if(fixed[a*2]) fixval[a*2] += addval[a];
        else           addval[a*2] += addval[a];
        if(fixed[a*2+1]) fixval[a*2+1] += addval[a];
        else             addval[a*2+1] += addval[a];
      }
      data[a*2]+=(coefsum[(st+ed)/2]-coefsum[st])*addval[a];
      data[a*2+1]+=(coefsum[ed]-coefsum[(st+ed)/2])*addval[a];
      addval[a]=0;
      return;
    }
  }
  
  inline void push(int a){
    int i,s=0,e=N;
    for(i=logN;i;i--){
      push_one(a>>i,s,e);
      if((a>>(i-1))&1)
        s=(s+e)/2;
      else
        e=(s+e)/2;
    }
  }
  
  inline void build(int a){
    int s=a-N,e=a-N+1;
    while(a>1){
      if(a%2)s-=e-s;
      else e+=e-s;a/=2;
      if(fixed[a]){
        data[a] = fixval[a] * (coefsum[e]-coefsum[s]);
      } else {
        data[a]=data[a*2]+data[a*2+1];
        if(addval[a]!=0)data[a]+=addval[a]*(coefsum[e]-coefsum[s]);
      }
    }
  }

  inline void change(int a, int b, T val){
    int c,d,s=a,t=b,sz=1;
    if(a>=b)return;
    c=(a+=N);
    d=(b+=N);
    push(a);
    push(b-1);
    if(a%2){
      data[a]=val*(coefsum[s+sz]-coefsum[s]);
      a++;
      s+=sz;
    }
    if(b%2){
      b--;
      data[b]=val*(coefsum[t]-coefsum[t-sz]);
      t-=sz;
    }
    a/=2;
    b/=2;
    while(a<b){
      sz*=2;
      if(a%2){
        fixed[a] = 1;
        fixval[a] = val;
        data[a++] = (coefsum[s+sz]-coefsum[s])*val;
        s+=sz;
      }
      if(b%2){
        b--;
        fixed[b] = 1;
        fixval[b] = val;
        data[b] = (coefsum[t]-coefsum[t-sz])*val;
        t-=sz;
      }
      a/=2;
      b/=2;
    }
    build(c);
    build(d-1);
  }
  
  inline void add(int a, int b, T val){
    int c,d,s=a,t=b,sz=1;
    if(a>=b)return;
    c=(a+=N);
    d=(b+=N);
    push(a);
    push(b-1);
    if(a%2){
      data[a]+=val*(coefsum[s+sz]-coefsum[s]);
      a++;
      s+=sz;
    }
    if(b%2){
      b--;
      data[b]+=val*(coefsum[t]-coefsum[t-sz]);
      t-=sz;
    }
    a/=2;
    b/=2;
    while(a<b){
      sz*=2;
      if(a%2){
        if(fixed[a]) fixval[a] += val; else addval[a]+=val;
        data[a++]+=(coefsum[s+sz]-coefsum[s])*val;
        s+=sz;
      }
      if(b%2){
        b--;
        if(fixed[b]) fixval[b]+=val; else addval[b]+=val;
        data[b]+=(coefsum[t]-coefsum[t-sz])*val;
        t-=sz;
      }
      a/=2;
      b/=2;
    }
    build(c);
    build(d-1);
  }
  
  inline T getSum(int a, int b){
    T res;
    int sz=1;
    a+=N;
    b+=N;
    push(a);
    push(b-1);
    res=0;
    while(a<b){
      if(a%2)res+=data[a++];
      if(b%2)res+=data[--b];
      a/=2;b/=2;
    }
    return res;
  }
};


template<class T> int coordinateCompress(int n, T arr[], int res[], void *mem){int i,k=0;pair<T,int>*r=(pair<T,int>*)mem;rep(i,n)r[i].first=arr[i],r[i].second=i;sort(r,r+n);if(res!=NULL){rep(i,n){if(i&&r[i].first!=r[i-1].first)k++;res[r[i].second]=k;}}else{rep(i,n){if(i&&r[i].first!=r[i-1].first)k++;arr[r[i].second]=k;}}return k+1;}
template<class T> int coordinateCompress(int n1, T arr1[], int n2, T arr2[], int res1[], int res2[], void *mem){int i,k=0;pair<T,int>*r =(pair<T,int>*)mem;rep(i,n1)r[i].first=arr1[i],r[i].second=i;rep(i,n2)r[n1+i].first=arr2[i],r[n1+i].second=n1+i;sort(r,r+n1+n2);rep(i,n1+n2){if(i&&r[i].first!=r[i-1].first) k++;if(r[i].second<n1){if(res1!=NULL)res1[r[i].second]=k;else arr1[r[i].second]=k;}else{if(res2!=NULL)res2[r[i].second-n1]=k;else arr2[r[i].second-n1]=k;}}return k+1;}


struct myrand32{
  unsigned x,y,z,w;

  myrand32(void){x=123456789,y=362436069,z=521288629,w=(unsigned)time(NULL);}
  myrand32(unsigned seed){x=123456789,y=362436069,z=521288629,w=seed;}
  inline unsigned get(void){unsigned t;t=(x^(x<<11));x=y;y=z;z=w;w=(w^(w>>19))^(t^(t>>8));return w;}
  inline double getUni(void){return get()/4294967296.0;}
  inline int get(int a){return (int)(a*getUni());}
  inline int get(int a, int b){return a+(int)((b-a+1)*getUni());}
  inline ll get(ll a){return(ll)(a*getUni());}
  inline ll get(ll a, ll b){return a+(ll)((b-a+1)*getUni());}
  inline double get(double a, double b){return a+(b-a)*getUni();}
  inline int getExp(int a){return(int)(exp(getUni()*log(a+1.0))-1.0);}
  inline int getExp(int a, int b){return a+(int)(exp(getUni()*log((b-a+1)+1.0))-1.0);}
};


char memarr[77000000]; void *mem = memarr;
#define MD 1000000000000000009LL

ll N;
int Q, X[300000];
ll L[300000], R[300000];

int LL[300000], RR[300000];

ll csum[700000];

int main(){
  int i, j, k, nn;
  ll res[5], tmp[5];
  lazySegtreeSumWithCoef<ll,ll> t[5];

  reader(&N,&Q);
  rep(i,Q) reader(X+i,L+i,R+i), R[i]++;

  rep(i,5) res[i] = 0;
  if(Q==0){ writerArr(res,5); return 0; }

  nn = coordinateCompress(Q, L, Q, R, LL, RR, mem);

  rep(i,5) mem = t[i].malloc(nn-1, mem);
  rep(i,5) t[i].setN(nn-1);

  rep(i,Q) csum[LL[i]] = L[i];
  rep(i,Q) csum[RR[i]] = R[i];
  rep(i,5) rep(j,nn-1) t[i].coef[j] = csum[j+1]-csum[j];

  rep(i,5) t[i].build();

  rep(i,Q){
    if(X[i]==0){
      rep(j,5) tmp[j] = t[j].getSum(LL[i],RR[i]);
      rep(j,5) if(tmp[j]>tmp[(j+1)%5]&&tmp[j]>tmp[(j+2)%5]&&tmp[j]>tmp[(j+3)%5]&&tmp[j]>tmp[(j+4)%5]) res[j] = (res[j]+tmp[j]) % MD;
    } else {
      rep(j,5){
        if(j==X[i]-1){
          t[j].add(LL[i],RR[i],1);
        } else {
          t[j].change(LL[i],RR[i],0);
        }
      }
    }
  }

  rep(i,5) tmp[i] = t[i].getSum(0,nn-1);
  rep(i,5) res[i] = (res[i] + tmp[i]) % MD;

  writerArr(res,5);

  return 0;
}
yukicoder

結果

テストケース

ソースコード
