QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #665215 | #7899. Say Hello to the Future | wrkwrk | TL | 977ms | 12472kb | C++20 | 9.7kb | 2024-10-22 09:58:36 | 2024-10-22 09:58:37 |
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,int lim){
p++;
lim++;
// cout<<p<<'?'<<q<<'\n';
while(p<=lim){
// 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),r);
}
}
}bb;
vector<pair<int,int>>z1,z2;
void solve(int l,int r){
if(l+1!=r){
int mid=(l+r)>>1;
solve(l,mid);
z1.clear();
z2.clear();
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});
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});
}
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],mid-1);
p++;
}
if(x.first-1>=l){
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);
z1.clear();
z2.clear();
// 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],mid-1);
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];
x=max(x,a[i]);
z2.push_back({i-x,i});
}
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],r);
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];
}
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: 7720kb
input:
5 1 3 2 1 2
output:
3 6 3 3 6
result:
ok 5 tokens
Test #2:
score: 0
Accepted
time: 893ms
memory: 12276kb
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 ...
result:
ok 200000 tokens
Test #3:
score: 0
Accepted
time: 905ms
memory: 12452kb
input:
200000 4065 9196 2588 18803 10818 17671 10483 13134 12147 19916 19382 19338 8864 7637 19542 14938 16362 7115 9159 9711 17907 17653 10175 3279 7471 3465 14016 13951 8676 2856 16709 5372 12237 18083 11052 16398 7140 9730 8800 18999 16808 8729 7608 6668 7049 6024 7892 18039 7278 12417 2440 13112 4039 5...
output:
47583147 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 345009231 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 370164779 3...
result:
ok 200000 tokens
Test #4:
score: 0
Accepted
time: 977ms
memory: 12464kb
input:
200000 1 1 1 1 4547 1 1 1 1 1 1 1 6329 1 1 19778 1 1 12258 1 1 1 1 1 18104 1 8123 1 329 1 1 1 1 1 1 1 1 4438 1 1 1 1 1 208 1 1 1 1 1 1 1 1 1 15603 1 1 1 1 1 1 1 1 1 1 5513 1 1 15427 1 1 1 1 1 1 1 18309 1 1 6333 1 1 1 1 1 1 1 1 1 13938 1 1 1 1 1 1 9229 1 1 1 1 1 1 1 1 1791 1 1 1 11747 1 1 1 1 8992 1 ...
output:
225508548 225508548 225508548 225508548 748768610 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 225508548 ...
result:
ok 200000 tokens
Test #5:
score: 0
Accepted
time: 967ms
memory: 12472kb
input:
200000 1 1 1 1 1 1 1 10166 1 1 9410 1 1 1 1 1 1 1 1 1 296 1 1 1 1 1 1 1 1 1 1 7392 4057 17616 1 1 1 1 3084 14799 1 1 13598 1 1 9848 1 1 1 1 1 8084 1 1 1 1 1 1 1 1 10519 1 1 1 1 1 14 1 1 1 1 1 1 1 1 1 1 14981 1 1 1 1 1 1 1 1 1 5144 7784 1 1 1 1 1 1 1 19661 1 14894 1 1 1 1 1 1 1 1 10449 1 1 1 16473 1 ...
output:
735167914 735167914 735167914 735167914 735167914 735167914 735167914 211149010 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 735167914 ...
result:
ok 200000 tokens
Test #6:
score: -100
Time Limit Exceeded
input:
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 1 6 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 1 1 1 1 1 1 1 1 6 1 1 1 2397 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 415221870 450552969 425969980 450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 450552969 ...