Submission #69366761

---

Source Code Expand

// 华风夏韵 洛水天依
// 天依宝宝可爱！> <

#include<bits/stdc++.h>

#define int long long
#define double long double
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rpe(i,a,b) for(int i=(a);i>=(b);--i)
#define repp(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define rpee(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define inf (int)(0x3f3f3f3f3f3f3f3f)
#define pii pair <int,int>
#define st first
#define nd second
#define mp make_pair
#define pb emplace_back
#define all(x) (x).begin(),(x).end()
#define mxele *max_element
#define mnele *min_element
#define gsum(l,r) accumulate((l),(r),0)
#define umap unordered_map
#define uset unordered_set
#define prque(a,b) priority_queue <a,vector<a>,b<a>>
#define popc __builtin_popcount
#define lowb lower_bound
#define uppb upper_bound

using namespace std;
bool memory_begin;

namespace fast_io{char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0,ny,precision=19;bool isEOF=0;unsigned long long pw10[20];il bool init_pw10(){pw10[0]=1ull;rep(i,1,19)pw10[i]=pw10[i-1]*10ull;return 1;}il char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}il int read(){int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc^EOF)nc==45&&(ny=-1);Bi=1;if(nc<0)return isEOF=1,nc;x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc^EOF)x=(x<<3)+(x<<1)+(nc^48),++Bi;return x*ny;}il void read(int &x){x=read();}il void read(char &x){while(nc=gc(),nc<33&&nc^EOF);nc<0&&(isEOF=1);x=nc;}il void read(pii&a){a.st=read(),a.nd=read();}il void read(double &x){pw10[0]||init_pw10();int a=read(),y=ny,b=(nc!='.')?0:read();x=(b?a+(double)b/pw10[Bi]*y:a);}il void read(string &s){s="";while(nc=gc(),nc<33&&nc^EOF);nc<0&&(isEOF=1);s+=nc;while(nc=gc(),nc>=33)s+=nc;}il signed read(char *s){char *t=s;while(nc=gc(),nc<33&&nc^EOF);nc<0&&(isEOF=1);*s++=nc;while(nc=gc(),nc>=33)*s++=nc;return s-t;}template <typename T,typename ... Args> il void read(T &x, Args &... y) {read(x);read(y...);}il void ot(){fwrite(sr,1,C+1,stdout);C=-1;}il void flush(){if(C>1<<22)ot();}il void pc(char c){sr[++C]=c;flush();}il void write(int x,char t='\0'){int y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);t=='\0'||(sr[++C]=t);flush();}il void write(char x,char t='\0'){sr[++C]=x,t=='\0'||(sr[++C]=t);flush();}il void write(pii a,char t='\0'){write(a.st,' '),write(a.nd,t);flush();}il void write(double x,char t='\0'){pw10[0]||init_pw10();write((int)x,'.'),write((int)((x-(int)x)*pw10[precision]),t);flush();}il void write(string s,char t='\0'){int l=s.size();rep(i,0,l-1)sr[++C]=s[i];t=='\0'||(sr[++C]=t);flush();}il void write(char *s,char t='\0'){int l=strlen(s);rep(i,0,l-1)sr[++C]=*s++;t=='\0'||(sr[++C]=t);flush();}template <typename T,typename ... Args> il void write(T x, Args ... y){write(x,' ');write(y...);}}
using fast_io::read,fast_io::write;
namespace _{template <typename T> il void r(T*a,int n){rep(i,1,n)read(a[i]);}template <typename T1,typename T2> il void r(T1 *a,T2 *b,int n){rep(i,1,n)read(a[i]),read(b[i]);}template <typename T1,typename T2,typename T3> il void r(T1 *a,T2 *b,T3 *c,int n){rep(i,1,n)read(a[i]),read(b[i]),read(c[i]);}template <typename T> il void r(T*a,int n,int m){rep(i,1,n)rep(j,1,m)read(a[i][j]);}template <typename T> il void r(vector<T>&a,int n){a.resize(n);rep(i,0,n-1)read(a[i]);}template <typename T> il void r(vector<T>*p,int m,bool op){int u,v;rep(i,1,m)read(u,v),p[u].pb(v),op||(p[v].pb(u),1);}template <typename T1,typename T2> il void r(vector<pair<T1,T2>>*p,int m,bool op){int u,v,w;rep(i,1,m)read(u,v,w),p[u].pb(v,w),op||(p[v].pb(u,w),1);}template <typename T> il void w(T*a,int n){rep(i,1,n-1)write(a[i],' ');n&&(write(a[n]),1),write('\n');}template <typename T> il void w(T*a,int n,int m){rep(i,1,n){rep(j,1,m-1)write(a[i][j],' ');m&&(write(a[i][m]),1),write('\n');}}template <typename T> il void w(vector<T>&a){rep(i,0,(int)a.size()-2)write(a[i],' ');!a.empty()&&(write(a.back()),1),write('\n');}}
#define is_debug 1
namespace dbg{template <typename T> il void arr(T*a,int n){if(!is_debug)return;rep(i,1,n-1)cerr<<a[i]<<' ';n&&(cerr<<a[n],1),cerr<<'\n';} template <typename T> il void arr(string s,T *a,int n){if(!is_debug)return;cerr<<s<<" : ";arr(a,n);}template <typename T> il void mat(T*a,int n,int m){if(!is_debug)return;rep(i,1,n){rep(j,1,m-1)cerr<<a[i][j]<<' ';m&&(cerr<<a[i][m],1),cerr<<'\n';}cerr<<'\n';} template <typename T> il void mat(string s,T *a,int n,int m){if(!is_debug)return;cerr<<s<<" :\n";mat(a,n,m);}template <typename T> il void vec(vector<T>a){if(!is_debug)return;rep(i,0,(int)a.size()-2)cerr<<a[i]<<' ';!a.empty()&&(cerr<<a.back(),1),cerr<<'\n';} template <typename T> il void vec(string s,vector <T> a){if(!is_debug)return;cerr<<s<<" : ";vec(a);}template <typename T> il void graV(vector<T>*p,int n){if(!is_debug)return;rep(u,1,n){cerr<<u<<" : ";rep(i,0,(int)p[u].size()-2)cerr<<p[u][i]<<' ';!p[u].empty()&&(cerr<<p[u].back(),1),cerr<<'\n';}cerr<<'\n';} template <typename T> il void graV(string s,vector <T> *p,int n){if(!is_debug)return;cerr<<s<<" :\n";graV(p,n);}template <typename T1,typename T2> il void graV(vector<pair<T1,T2>>*p,int n){if(!is_debug)return;rep(u,1,n){cerr<<u<<" : ";rep(i,0,(int)p[u].size()-2)cerr<<p[u][i].st<<','<<p[u][i].nd<<' ';!p[u].empty()&&(cerr<<p[u].back().st<<','<<p[u].back().nd,1),cerr<<'\n';}cerr<<'\n';} template <typename T1,typename T2> il void graV(string s,vector <pair<T1,T2>> *p,int n){if(!is_debug)return;cerr<<s<<" :\n";graV(p,n);}template <typename T> il void graE(vector<T>*p,int n,bool op){if(!is_debug)return;rep(u,1,n)for(auto v:p[u])(op||u<v)&&(cerr<<u<<' '<<v<<'\n',1);cerr<<'\n';} template <typename T> il void graE(string s,vector <T> *p,int n,bool op){if(!is_debug)return;cerr<<s<<" :\n";graE(p,n,op);}template <typename T1,typename T2> il void graE(vector<pair<T1,T2>>*p,int n,bool op){if(!is_debug)return;rep(u,1,n)for(auto [v,w]:p[u])(op||u<v)&&(cerr<<u<<' '<<v<<' '<<w<<'\n',1);cerr<<'\n';} template <typename T1,typename T2> il void graE(string s,vector <pair<T1,T2>> *p,int n,bool op){if(!is_debug)return;cerr<<s<<" :\n";graE(p,n,op);}}

const int N=6e5+5,M=6e5+5,V=6e5+5,mod=1e9+7;
const int dx[10]={0,0,1,0,-1,1,1,-1,-1},dy[10]={0,1,0,-1,0,1,-1,1,-1};
const double eps=1e-9;

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
il double gtime(){return clock()*1e3/CLOCKS_PER_SEC;}
template <typename T> il void clr(T &x){T().swap(x);}
template <typename T1,typename T2> il T1& add(T1 &a,T2 b){a+=b,a>=0?(a>=mod&&(a-=mod)):(a<-mod?a+=mod<<1:a+=mod);return a;}
template <typename T1,typename T2> il T1& chmax(T1 &a,T2 b){return a<b&&(a=b,1),a;}
template <typename T1,typename T2> il T1& chmin(T1 &a,T2 b){return a>b&&(a=b,1),a;}
//il long long mod_(const long long &x){unsigned long long ux=(x>=0?x:-x),r=ux-(__uint128_t(ux)*9920937979283557439ull>>93)*998244353; return x>=0?r:mod-r;}
il long long mod_(const long long &x){unsigned long long ux=(x>=0?x:-x),r=ux-(__uint128_t(ux)*9903520244958400484ull>>93)*1000000007; return x>=0?r:mod-r;}
//il long long mod_(const long long &x){return x<0?x%mod+mod:x%mod;}

#define multiple_test 0
int __T=1;

int n,a[N],f[2][N],s[2][N];

il void solve(int __Ti)
{
//    double time_begin=gtime();
	
	read(n),_::r(a,n);
	
	f[0][1]=s[0][1]=1;
	bool fl=0;
	rep(i,2,n)
	{
		fl=!fl;
		rep(j,0,i+1) f[fl][j]=s[fl][j]=0;
		rep(j,1,i)
		{
			if(a[i]>a[i-1]) f[fl][j]=mod_(s[!fl][i-1]-s[!fl][j-1]);
			else if(a[i]<a[i-1]) f[fl][j]=s[!fl][j-1];
			else f[fl][j]=s[!fl][i-1];
			s[fl][j]=mod_(s[fl][j-1]+f[fl][j]);
		}
	}
	
	write(s[fl][n]);
	
//    cerr<<"task "<<__Ti<<" : time = "<<gtime()-time_begin<<" ms\n";
}

il void init()
{
	
}

bool memory_end;
signed main()
{
//    freopen(".in","r",stdin),freopen(".out","w",stdout);
//    ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr);
	fprintf(stderr,"memory = %.3lf MB\n\n",abs(&memory_end-&memory_begin)/1048576.);
	init(); multiple_test&&(read(__T),1);
	rep(__Ti,1,__T) solve(__Ti);
//    int __Ti=0; while(read(n),!fast_io::isEOF) solve(++__Ti);
	fprintf(stderr,"\ntime = %.3Lf ms\n",gtime());
	return fast_io::ot(),0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve(long long int)’:
Main.cpp:58:19: warning: unused parameter ‘__Ti’ [-Wunused-parameter]
   58 | il void solve(int __Ti)
      |                   ^

Judge Result