QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#498542#5057. Prof. Pang's sequencePhysics212303Compile Error//C++172.6kb2024-07-30 15:58:022024-07-30 15:58:02

Judging History

你现在查看的是最新测评结果

  • [2024-07-30 15:58:02]
  • 评测
查看
  • [2024-07-30 15:58:02]
  • 提交

answer

#pragma GCC target("sse,sse2,sse3,sse4,popcnt,avx,avx2,tune=native")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef array<ll,3> S;
typedef array<array<ll,3>,3> F;
inline int read(){
  int x=0; char c=getchar();
  while(!isdigit(c))c=getchar();
  while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
  return x;
}
inline S operator +(S x,S y){
  S z;
  for(int i=0;i<3;i++)
    z[i]=x[i]+y[i];
  return z;
}
inline S e(){
  return {1,0,0};
}
inline S operator *(S x,F f){
  S y;
  for(int i=0;i<3;i++)
    for(int j=y[i]=0;j<3;j++)
      y[i]+=x[j]*f[j][i];
  return y;
}
inline S operator *=(S &x,F f){
  return x=x*f;
}
inline F operator *(F f,F g){
  F r;
  for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
      for(int k=r[i][j]=0;k<3;k++)
        r[i][j]+=f[i][k]*g[k][j];
  return r;
}
inline F operator *=(F &f,F g){
  return f=f*g;
}
inline F id(){
  return {{{1,0,0},{0,1,0},{0,0,1}}};
}
class segtree{
  private:
    vector<pii> B;
    vector<S> R;
    vector<F> T;
  public:
    inline void pushup(int u){
      R[u]=R[u<<1]+R[u<<1|1];
    }
    inline void pushdown(int u){
      if(T[u]!=id()){
        R[u<<1]*=T[u],R[u<<1|1]*=T[u];
        T[u<<1]*=T[u],T[u<<1|1]*=T[u],T[u]=id();
      }
    }
    segtree(int n){
      B.resize(n<<2),R.resize(n<<2,e()),T.resize(n<<2,id());
      function<void(int,int,int)> build=[&](int u,int l,int r){
        if(B[u]=make_pair(l,r);l==r)return;
        int m=l+r>>1;
        build(u<<1,l,m),build(u<<1|1,m+1,r);
        pushup(u);
      };
      build(1,0,n-1);
    }
    inline void update(int u,int l,int r,F f){
      if(B[u].first>r||B[u].second<l)return;
      if(l<=B[u].first&&B[u].second<=r){
        R[u]*=f,T[u]*=f; return;
      }
      pushdown(u);
      update(u<<1,l,r,f),update(u<<1|1,l,r,f);
      pushup(u);
    }
    inline S query(int u,int l,int r){
      if(B[u].first>r||B[u].second<l)return e();
      if(l<=B[u].first&&B[u].second<=r)return R[u];
      pushdown(u);
      return query(u<<1,l,r)+query(u<<1|1,l,r);
    }
};
int main(){
  int n=read();
  vector<int> a(n),l(n,-1);
  for(auto &i:a)i=read()-1;
  int m=read();
  vector<vector<pii> > q(n);
  vector<ll> w(m);
  for(int i=0;i<m;i++){
    int l=read()-1,r=read()-1;
    q[r].emplace_back(l,i);
  }
  segtree t(n);
  for(int i=0;i<n;l[a[i]]=i,i++){
    t.update(1,l[a[i]]+1,i,{{{0,1,1},{1,0,0},{0,0,1}}});
    if(~l[a[i]])t.update(1,0,l[a[i]],{{{1,0,0},{0,1,1},{0,0,1}}});
    for(auto [l,j]:q[i])w[j]=t.query(1,l,i)[2];
  }
  for(ll i:w)printf("%lld\n",i);
  return 0;
}
Source code, Language: C++17

Details 

In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148,
                 from /usr/include/c++/13/ext/atomicity.h:35,
                 from /usr/include/c++/13/bits/ios_base.h:39,
                 from /usr/include/c++/13/streambuf:43,
                 from /usr/include/c++/13/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/13/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54,
                 from answer.code:2:
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  102 | __gthrw(pthread_once)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  103 | __gthrw(pthread_getspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  104 | __gthrw(pthread_setspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  106 | __gthrw(pthread_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  107 | __gthrw(pthread_join)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  108 | __gthrw(pthread_equal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  109 | __gthrw(pthread_self)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  110 | __gthrw(pthread_detach)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  112 | __gthrw(pthread_cancel)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  114 | __gthrw(sched_yield)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  116 | __gthrw(pthread_mutex_lock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  117 | __gthrw(pthread_mutex_trylock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  119 | __gthrw(pthread_mutex_timedlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:121:1: error: attribute value ‘t...
English 繁體中文 简体中文

Server Time: 2024-12-04 22:28:59 | OpenSource Project