QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#608112#9245. Bracket SequenceXY_ElevenWA 1452ms381712kbC++236.5kb2024-10-03 18:35:022024-10-03 18:35:02

Judging History

This is the latest submission verdict.

  • [2024-10-03 18:35:02]
  • Judged
  • Verdict: WA
  • Time: 1452ms
  • Memory: 381712kb
Show
  • [2024-10-03 18:35:02]
  • Submitted

answer

#include <bits/stdc++.h>
// #include <windows.h>
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
using namespace std;
//#pragma GCC optimize(3)
#define DB double
#define LL long long
#define ULL unsigned long long
#define in128 __int128
#define cint const int
#define cLL const LL
#define For(z,e1,e2) for(int z=(e1);z<=(e2);z++)
#define Rof(z,e1,e2) for(int z=(e2);z>=(e1);z--)
#define For_(z,e1,e2) for(int z=(e1);z<(e2);z++)
#define Rof_(z,e1,e2) for(int z=(e2);z>(e1);z--)
#define inint(e) scanf("%d",&e)
#define inll(e) scanf("%lld",&e)
#define inpr(e1,e2) scanf("%d%d",&e1,&e2)
#define in3(e1,e2,e3) scanf("%d%d%d",&e1,&e2,&e3)
#define outint(e) printf("%d\n",e)
#define outint_(e) printf("%d%c",e," \n"[i==n])
#define outint2_(e,e1,e2) printf("%d%c",e," \n"[(e1)==(e2)])
#define outll(e) printf("%lld\n",e)
#define outll_(e) printf("%lld%c",e," \n"[i==n])
#define outll2_(e,e1,e2) printf("%lld%c",e," \n"[(e1)==(e2)])
#define exc(e) if(e) continue
#define stop(e) if(e) break
#define ret(e) if(e) return
#define ll(e) (1ll*(e))
#define pb push_back
#define ft first
#define sc second
#define pii pair<int,int> 
#define pli pair<LL,int> 
#define vct vector 
#define clean(e) while(!e.empty()) e.pop()
#define all(ev) ev.begin(),ev.end()
#define sz(ev) ((int)ev.size())
#define debug(x) printf("%s=%d\n",#x,x)
#define x0 __xx00__
#define y1 __yy11__
#define ffo fflush(stdout)
cLL mod=998244353,G=404;
// cLL mod[2]={1686688681ll,1666888681ll},base[2]={166686661ll,188868881ll};
template <typename Type> void get_min(Type &w1,const Type w2) { if(w2<w1) w1=w2; } template <typename Type> void get_max(Type &w1,const Type w2) { if(w2>w1) w1=w2; }
template <typename Type> Type up_div(Type w1,Type w2) { return (w1/w2+(w1%w2?1:0)); }
template <typename Type> Type gcd(Type X_,Type Y_) { Type R_=X_%Y_; while(R_) { X_=Y_; Y_=R_; R_=X_%Y_; } return Y_; } template <typename Type> Type lcm(Type X_,Type Y_) { return (X_/gcd(X_,Y_)*Y_); }
template <typename Type> Type md(Type w1,const Type w2=mod) { w1%=w2; if(w1<0) w1+=w2; return w1; } template <typename Type> Type md_(Type w1,const Type w2=mod) { w1%=w2; if(w1<=0) w1+=w2; return w1; }
void ex_gcd(LL &X_,LL &Y_,LL A_,LL B_) { if(!B_) { X_=1ll; Y_=0ll; return ; } ex_gcd(Y_,X_,B_,A_%B_); X_=md(X_,B_); Y_=(1ll-X_*A_)/B_; } LL inv(LL A_,LL B_=mod) { LL X_=0ll,Y_=0ll; ex_gcd(X_,Y_,A_,B_); return X_; }
template <typename Type> void add(Type &w1,const Type w2,const Type M_=mod) { w1=md(w1+w2,M_); } void mul(LL &w1,cLL w2,cLL M_=mod) { w1=md(w1*md(w2,M_),M_); } template <typename Type> Type pw(Type X_,Type Y_,Type M_=mod) { Type S_=1; while(Y_) { if(Y_&1) mul(S_,X_,M_); Y_>>=1; mul(X_,X_,M_); } return S_; }
template <typename Type> Type bk(vector <Type> &V_) { auto T_=V_.back(); V_.pop_back(); return T_; } template <typename Type> Type tp(stack <Type> &V_) { auto T_=V_.top(); V_.pop(); return T_; } template <typename Type> Type frt(queue <Type> &V_) { auto T_=V_.front(); V_.pop(); return T_; }
template <typename Type> Type bg(set <Type> &V_) { auto T_=*V_.begin(); V_.erase(V_.begin()); return T_; } template <typename Type> Type bk(set <Type> &V_) { auto T_=*prev(V_.end()); V_.erase(*prev(V_.end())); return T_; }
mt19937 gen(time(NULL)); int rd() { return abs((int)gen()); }
int rnd(int l,int r) { return rd()%(r-l+1)+l; }
void main_init()
{
}
cint N=1.02e5,Q_=1.02e6,D=20;
int n,Q;
char str[N];
bool vis[N];
#define Query array<int,4>
struct Node
{
    LL x,y1,y2,s1,s2;
    void Add(Node &A,int w1,int w2)
    {
        add(x,A.x);
        add(y1,A.y1+A.x*w1);
        add(s1,A.y2*w1);
        add(y2,A.y2+A.x*w2);
        add(s2,A.y1*w2);
    }
};
array <Node,D<<1|1> f[N],f2[N];
LL ans[N];
void solve(int l,int r,vct<Query> q1,vct<Query> q2)
{
    ret(l>=r||(q1.empty()&&q2.empty()));
    int mid=l+r>>1;
    vct<Query> q1l,q1r,q2l,q2r,tmp;
    tmp.clear();
    for(auto i:q1)
        if(i[1]<=mid&&i[2]>mid) tmp.pb(i);
        else if(i[2]<=mid) q1l.pb(i);
        else q1r.pb(i);
    tmp.swap(q1);
    tmp.clear();
    for(auto i:q2)
        if(i[1]<=mid&&i[2]>mid) tmp.pb(i);
        else if(i[2]<=mid) q2l.pb(i);
        else q2r.pb(i);
    tmp.swap(q2);
    For(opt,0,1)
    {
        For(i,0,D<<1) f[mid+1][i]={0ll,0ll,0ll,0ll}; f[mid+1][0]={1ll,0ll,0ll,0ll};
        Rof(k,l,mid)
        {
            f[k]=f[k+1];
            if(vis[k]==opt) For_(i,0,D) f[k][i+1<<1].Add(f[k][i<<1|1],vis[k]?0:k,vis[k]?k:0);
            else For_(i,0,D) f[k][i<<1|1].Add(f[k][i<<1],vis[k]?0:k,vis[k]?k:0);
        }
        For(i,0,D<<1) f2[mid][i]={0ll,0ll}; f2[mid][0]={1ll,0ll};
        For(k,mid+1,r)
        {
            f2[k]=f2[k-1];
            if(vis[k]!=opt) For_(i,0,D) f2[k][i+1<<1].Add(f2[k][i<<1|1],vis[k]?0:k,vis[k]?k:0);
            else For_(i,0,D) f2[k][i<<1|1].Add(f2[k][i<<1],vis[k]?0:k,vis[k]?k:0);
        }
        for(auto [id,l,r,d]:q1)
        {
            For(i,0,d<<1) if(!((i^opt)&1))
                add(ans[id],f[l][i].x*f2[r][(d<<1)-i].x);
        }
        for(auto [id,l,r,d]:q2)
        {
            For(i,0,d<<1) if(!((i^opt)&1))
            {
                // (i-l+1)*(r-j+1)
                LL x1=f[l][i].x,y1=f[l][i].y1,x2=f2[r][(d<<1)-i].x,y2=f2[r][(d<<1)-i].y2;
                if(!i)
                {
                    y1=f2[r][(d<<1)-i].y1;
                    add(ans[id],(-1ll*(l-1)*(r+1))%mod*x2+(l-1)*y2+y1*(r+1)-f2[r][(d<<1)-i].s2);
                }
                else if(i==(d<<1))
                {
                    y2=f[l][i].y2;
                    add(ans[id],(-1ll*(l-1)*(r+1))%mod*x1+(l-1)*y2+y1*(r+1)-f[l][i].s1);
                }
                else add(ans[id],((-(l-1)*x1+y1)%mod)*(((r+1)*x2-y2)%mod));
                // printf("%d,%d:%lld,%lld*%lld,%lld=%lld\n",i,(d<<1)-i,x1,y1,x2,y2,((-(l-1)*x1+y1)%mod)*(((r+1)*x2-y2)%mod)%mod);
            }
        }
    }
    solve(l,mid,q1l,q2l),solve(mid+1,r,q1r,q2r);
}
void main_solve()
{
    scanf("%d%d%s",&n,&Q,str+1);
    For(i,1,n) vis[i]=str[i]-'(';
    vct<Query> q1,q2;
    For(qid,1,Q)
    {
        int opt,l,r,d; scanf("%d%d%d%d",&opt,&l,&r,&d);
        exc(l==r);
        if(opt==1) q1.pb({qid,l,r,d});
        else q2.pb({qid,l,r,d});
    }
    solve(1,n,q1,q2);
    For(i,1,Q) outll(ans[i]);
}
int main()
{
    // ios::sync_with_stdio(0); cin.tie(0);
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // srand(time(NULL));
    main_init();
    // int _; inint(_); For(__,1,_) // T>1 ?
        // printf("\n------------\n\n"),
        main_solve();
    return 0;
}
/*

*/
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7984kb

input:

5 20
(()()
1 1 2 1
1 1 3 1
1 1 4 1
1 1 5 1
1 2 3 1
1 2 4 1
1 2 5 1
1 3 4 1
1 3 5 1
1 4 5 1
2 1 3 1
2 1 4 1
2 1 5 1
2 2 3 1
2 2 4 1
2 2 5 1
2 3 5 1
2 4 5 1
1 1 5 2
2 1 5 2

output:

0
2
2
5
1
1
3
0
1
1
3
6
16
1
2
7
2
1
2
3

result:

ok 20 lines

Test #2:

score: -100
Wrong Answer
time: 1452ms
memory: 381712kb

input:

100000 1000000
)())))))())()()()(())))()())))()))))())))))()(()()))()()))((()()))()))((())(())())()(()))))()))(()()()()()(())(()((()))()((()(()))()))()))()()))(())))()()(()(()())())((()((()((())()(()()))())(())())())))))))((())(((()(())())))(()(((())())))(((((((((()))()())())(()))(())()()()()((()())...

output:

807252937
43419252
883174699
122104482
597950507
727102669
185350091
253876231
392529556
736028324
426329153
227116734
315566541
444655931
76394527
216715407
972560363
267476807
597971868
302716489
498728925
1522883
884430300
78253278
580163375
311733437
605305965
986700007
340780822
973620960
45810...

result:

wrong answer 2nd lines differ - expected: '333653009', found: '43419252'
English 繁體中文 简体中文

Server Time: 2025-02-08 20:37:45 | OpenSource Project