QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #665197 | #7899. Say Hello to the Future | wrkwrk | TL | 2ms | 8772kb | C++20 | 10.1kb | 2024-10-22 09:35:03 | 2024-10-22 09:35:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
bool st;
namespace _wrk{;
template<int mod>
struct modint{
int num;
const static __uint128_t brt=((__uint128_t)(1)<<(64))/mod;
modint(){
num=0;
}
modint(int x){
num=x%mod;
}
modint(long long x){
num=x%mod;
}
modint<mod>operator=(int x){
num=x%mod;
return (*this);
}
modint<mod>operator=(long long x){
num=x%mod;
return (*this);
}
modint<mod>operator=(modint<mod>x){
num=x.num;
return (*this);
}
modint<mod> operator+(modint<mod> c)const{
long long x=num+c.num;
return x>=mod?x-mod:x;
}
modint<mod> operator-(modint<mod> c)const{
long long x=num-c.num;
return x<0?x+mod:x;
}
modint<mod>operator*(modint<mod>c)const{
long long x=(long long)num*c.num;
x=x-mod*(brt*x>>64);
while(x>=mod)x-=mod;
return x;
}
modint<mod>fpof(long long x)const{
if(x<0)return inv().fpof(-x);
if(x==0)return 1;
auto c=((*this)*(*this)).fpof(x/2);
if(x&1)return c*(*this);
else return c;
}
struct modint_pow{
int pf;
modint_pow(int x){
pf=x;
}
modint_pow(modint<mod> x){
pf=x.num;
}
modint_pow operator+(modint_pow x){
return pf+x.pf;
}
};
modint_pow operator*(){
return modint_pow(num);
}
modint<mod> operator*(modint_pow x){
return (*this).fpof(x.pf);
}
modint<mod>inv()const{
return fpof(mod-2);
}
modint<mod>operator/(modint<mod>c){
return (*this)*c.inv();
}
operator int(){
return num;
}
modint<mod>operator+=(modint<mod> c){
return (*this)=(*this)+c;
}
modint<mod>operator-=(modint<mod> c){
return (*this)=(*this)-c;
}
modint<mod>operator*=(modint<mod> c){
return (*this)=(*this)*c;
}
modint<mod>operator/=(modint<mod> c){
return (*this)=(*this)/c;
}
modint<mod>operator-(){
return mod-num;
}
friend ostream& operator<<(ostream &w,modint<mod>&&x){
w<<x.num;
return w;
}
friend istream& operator>>(istream &w,modint<mod>&x){
w>>x.num;
x.num%=mod;
return w;
}
bool operator==(modint<mod>x){
return num==x.num;
}
};
template<int mod,class type>
modint<mod>operator+(type a,modint<mod>b){
return modint<mod>(a)+b;
}
template<int mod,class type>
modint<mod>operator-(type a,modint<mod>b){
return modint<mod>(a)-b;
}
template<int mod,class type>
modint<mod>operator*(type a,modint<mod>b){
return modint<mod>(a)*b;
}
template<int mod,class type>
modint<mod>operator/(type a,modint<mod>b){
return modint<mod>(a)/b;
}
#define int long long
template<class type,int N>
struct matrix{
type a[N+2][N+2];
int n;
type* operator[](int pos){
return a[pos];
}
matrix<type,N> operator*(matrix<type,N>b){
matrix<type,N>ans;
ans.n=n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
ans[i][j]+=a[i][k]*b[k][j];
}
}
}
return ans;
}
};
template<class type>
type fp(type a,int b){
if(b==0)return type();
if(b==1)return a;
type w=fp(a*a,b/2);
if(b%2)return w*a;
return w;
}
template<class type,int N>
struct backup_array{
type name[N+5];
vector<vector<pair<int,int>>>cc;
void new_array(){
cc.push_back(vector<pair<int,int>>());
}
backup_array(){
cc.resize(1);
}
struct x{
int id;
type* name;
vector<vector<pair<int,int>>> &cc;
operator type(){
return name[id];
}
type operator=(type w){
cc.back().push_back({id,name[id]});
name[id]=w;
return w;
}
};
x operator[](int pos){
return {pos,name,cc};
}
void backup(){
reverse(cc.back().begin(),cc.back().end());
for(auto &x:cc.back()){
name[x.first]=x.second;
}
cc.pop_back();
}
};
template<class type,int N>
struct Math{
type jc[N+5],inv[N+5],invjc[N+5];
Math(){
jc[0]=jc[1]=inv[1]=invjc[1]=invjc[0]=1;
for(int i=2;i<=N;i++){
jc[i]=jc[i-1]*type(i);
}
invjc[N]=type(1)/jc[N];
for(int i=N-1;i>=2;i--){
invjc[i]=invjc[i+1]*type(i+1);
}
for(int i=1;i<=N;i++){
inv[i]=invjc[i]*jc[i-1];
}
}
type binom(int a,int b){
return jc[a]*invjc[b]*invjc[a-b];
}
type catalan(int n){
return binom(2*n,n)/type(n+1);
}
};
template<class type,int num,int maxnum>
struct pows{
type w[maxnum+5];
pows(){
w[0]=type(1);
for(int i=1;i<=maxnum;i++)w[i]=w[i-1]*type(num);
}
type operator[](int pos){
return w[pos];
}
};
#ifdef use_seg_tree
template<class type,class laz_type,int len>
struct segment_tree{
type a[len<<2];
laz_type laz[len<<2];
void pushup(int now){
PUSHUP_VALUE
}
void pushdown(int now,int l,int r){
PUSHDOWN_VALUE
}
void build(int now,int l,int r){
if(l+1==r){
FIRST_VALUE
return;
}
LAZ_CLEAR
int mid=(l+r)>>1;
build(now<<1,l,mid);
build(now<<1|1,mid,r);
pushup(now);
}
void do1(int now,int l,int r,int L,int R,...){
if(l+1!=r)pushdown(now,l,r);
if(R<=l||r<=L)return;
if(L<=l&&r<=R){
FULL_BLOCK_VALUE
return;
}
int mid=(l+r)>>1;
do1(now<<1,l,mid,L,R,...);
do1(now<<1|1,mid,r,L,R,...);
pushup(now);
}
void do1_one(int now,int l,int r,int p,...){
if(l+1!=r)pushdown(now,l,r);
if(l+1==r){
DO1_VALUE
return;
}
int mid=(l+r)>>1;
if(p<mid)do1_one(now<<1,l,mid,p,...);
else do1_one(now<<1|1,mid,r,p,...);
pushup(now);
}
type qu1(int now,int l,int r,int L,int R){
if(l+1!=r)pushdown(now,l,r);
if(R<=l||r<=L)return BASE_VALUE
if(L<=l&&r<=R)return a[now];
int mid=(l+r)>>1;
return RETURN_VALVE qu1(now<<1,l,mid,L,R)+qu1(now<<1|1,mid,r,L,R);
}
type qu1_one(int now,int l,int r,int p){
if(l+1!=r)pushdown(now,l,r);
if(l+1==r)return a[now];
int mid=(l+r)>>1;
if(p<mid)return qu1_one(now<<1,l,mid,p);
else return qu1_one(now<<1|1,mid,r,p);
}
};
#endif
#define mod 998244353
#define mint modint<mod>
//pows<mint,2,1000006>tp;
//Math<mint,1000006>math;
//vector<int>g[1000006]
int a[200005];
mint dp[200005];
mint d1p[200005];
mint d2p[200005];
mint ans[200005];
//dp i end at i-1 sol
struct bit{
mint a[200005];
int lowbit(int x){
return x&(-x);
}
void ad(int p,mint q){
p++;
// cout<<p<<'?'<<q<<'\n';
while(p<=200002){
// if(p<=4)cout<<p<<'r'<<a[p]<<'\n';
a[p]+=q;
// if(p<=4)cout<<p<<'r'<<a[p]<<'\n';
p+=lowbit(p);
}
}
mint ge(int l,int r){
if(l>r)return 0;
// cout<<l<<'\\'<<r<<endl;
if(l){
return ge(0,r)-ge(0,l-1);
}
r++;
mint ans=0;
int c=r;
while(r){
ans+=a[r];
// cout<<r<<'+'<<a[r]<< endl;
r-=lowbit(r);
}
// cout<<c<<'!'<<ans<<'\n';
return ans;
}
void clear(int l,int r){
for(int i=l;i<=r;i++){
ad(i,-ge(i,i));
}
}
}bb;
void solve(int l,int r){
if(l+1!=r){
int mid=(l+r)>>1;
solve(l,mid);
vector<pair<int,int>>z1,z2;
int x=1;
//r-maxr+1>=l
//r>=l+maxl-1
//l<=r-maxr+1
for(int i=mid-1;i>=l;i--) {
z1.push_back({i+x,i});
// cout<<i<<' '<<i+x<<">>>"<<endl;
x=max(x,a[i]);
}
x=1;
for(int i=mid;i<r;i++){
x=max(x,a[i]);
z2.push_back({i-x+1,i});
// cout<<l<<' '<<r<<' '<<i<<' '<<x<<'-'<<i-x+1<<'\n';
}
sort(z1.begin(),z1.end());
bb.clear(l,mid-1);
int p=0;
for(auto x:z2){
while(p!=z1.size()&&z1[p].first<=x.second){
bb.ad(z1[p].second,dp[z1[p].second]);
// cout<<l<<' '<<r<<' '<<z1[p].first<<' '<<z1[p].second<<','<<dp[z1[p].second]<<'\n';
p++;
}
if(x.first-1>=l){
// cout<<l<<' '<<r<<' '<<x.second<<' '<<l<<' '<<x.first<<' '<<x.first<<' '<<mid-1<<' '<<min(x.first-1,mid-1)<<' '<<bb.ge(l,min(x.first-1,mid-1))<<'\n';
// if(x.second==3)cout<<"!!!!!!!!!!";
dp[x.second]+=bb.ge(l,min(x.first-1,mid-1));
}
}
solve(mid,r);
}
// [l,mid) ok
}
void solvep(int l,int r){
if(l+1!=r){
int mid=(l+r)>>1;
solvep(l,mid);
solvep(mid,r);
vector<pair<int,int>>z1,z2;
//r-maxr+1>=l
//r>=l+maxl-1
//l<=r-maxr+1
int x=1;
for(int i=mid-1;i>=l;i--) {
z1.push_back({i+x,i});
x=max(x,a[i]);
}
sort(z1.begin(),z1.end());
int p=0;
bb.clear(l,mid-1);
multiset<int>pc={1,1};
int mapo=0;
x=1;
for(int i=mid;i<r;i++){
while(p!=z1.size()&&z1[p].first<=i){
bb.ad(z1[p].second,d1p[z1[p].second]);
// cout<<l<<' '<<r<<' '<<z1[p].first<<' '<<z1[p].second<<','<<dp[z1[p].second]<<'\n';
p++;
}
pc.insert(a[i]);
pc.erase(pc.begin());
if(a[i]>a[mapo])mapo=i;
ans[mapo]+=bb.ge(min(max(l,i-a[mapo]+1),mid),min(max(l-1,i-*pc.begin()),mid-1))*d2p[i+1];
// cout<<l<<','<<r<<' '<<mapo<<' '<<bb.ge(min(max(l,i-a[mapo]+1),mid),min(max(l-1,i-*pc.begin()),mid-1))*d2p[i+1]<<'\n';
x=max(x,a[i]);
z2.push_back({i-x,i});
// cout<<l<<' '<<r<<' '<<i<<' '<<x<<'-'<<i-x+1<<'\n';
}
bb.clear(mid,r);
sort(z2.begin(),z2.end(),greater<pair<int,int>>());
p=0;
mapo=0;
pc={1,1};
for(int i=mid-1;i>=l;i--){
while(p!=z2.size()&&z2[p].first>=i){
bb.ad(z2[p].second,d2p[z2[p].second+1]);
// cout<<l<<' '<<r<<' '<<z1[p].first<<' '<<z1[p].second<<','<<dp[z1[p].second]<<'\n';
p++;
}
if(i!=mid-1){
ans[mapo]+=bb.ge(max(min(i+*pc.begin(),r),mid),max(min(i+a[mapo]-1,r-1),mid-1))*d1p[i];
// cout<<l<<' '<<r<<' '<<mapo<<' '<<bb.ge(min(max(i+*pc.begin(),r),mid),min(mj(i+a[mapo]-1,r-1),mid-1))*d1p[i]<<' '<<min(max(i+*pc.begin(),r),mid)<<' '<<min(m(i+a[mapo]-1,r-1),mid-1)<<' '<<*pc.begin()<<' '<<mid<<' '<<i+a[mapo]<<'\n';
}
if(a[i]>a[mapo])mapo=i;
pc.insert(a[i]);
pc.erase(pc.begin());
}
}
// [l,mid) ok
}
//mint ans[200005];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// freopen("c.in","r",stdin);
// freopen("c.out","w",stdout);
int n;
cin>>n;
// if(n>=10000)assert(0);
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[0]=1;
solve(0,n+1);
swap(dp,d1p);
reverse(a+1,a+1+n);
dp[0]=1;
solve(0,n+1);
reverse(a+1,a+1+n);
swap(dp,d2p);
reverse(d2p,d2p+2+n);
//
// for(int i=0;i<=n+1;i++){
// cout<<i<<' '<<d1p[i]<<' '<<d2p[i]<<'\n';
// }
for(int i=1;i<=n;i++){
ans[i]=d1p[n];
}
solvep(0,n+1);
for(int i=1;i<=n;i++){
cout<<ans[i]<<' ';
}
// cout<<dp[n];
return 0;
}
}
bool en;
signed main(){
#ifdef LOCAL_WRK
cerr<<"[Static Memory : "<<fixed<<((&st)-(&en))/1048576.0<<"MB]"<<endl;
#endif
return _wrk::main();
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 8772kb
input:
5 1 3 2 1 2
output:
3 6 3 3 6
result:
ok 5 tokens
Test #2:
score: -100
Time Limit Exceeded
input:
200000 15922 15391 11782 4758 1973 19909 16800 6438 3821 986 18599 2011 338 19886 12401 4169 11143 12665 3230 12565 15065 15056 5090 16908 13677 12634 11435 1425 8647 3876 10694 12256 3853 19901 5723 11065 6147 13613 13768 15794 14993 5819 8117 13871 14708 15099 7152 9810 14438 10557 3209 1265 13915...
output:
157122482 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 826457499 ...