QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#349995	#8279. Segment Tree	isaunoya^#	WA	5ms	36640kb	C++14	2.2kb	2024-03-10 11:25:04	2024-03-10 11:25:05

Judging History

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

[2024-03-10 11:25:05]
评测

测评结果：WA
用时：5ms
内存：36640kb

查看

[2024-03-10 11:25:04]
提交

answer

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 4e5 + 5,p=998244353; bool fl[N];
int X[N],k=1,c,L[N],R[N],ch[N][2],f[N],F[N];long long dp[N][3]; vector<int>vt[N],vw[N];
//0:limit
//1:no occupy
//2:occupy
int lowbit(int u){
  return (u&(-u));
}
void add(int u,int s){
  while(u<=n) f[u]+=s,u+=lowbit(u);
}
int query(int u){
  int ans=0;
  while(u>0){
    ans+=f[u],u-=lowbit(u);
  }
  return ans;
}
void dfs(int l,int r,int t){
  vw[r].push_back(t);
  L[t]=l,R[t]=r;
  if(l==r) return;
  int d=X[++c]-1;
  ch[t][0]=++k;
  dfs(l,d,k);
  ch[t][1]=++k;
  dfs(d+1,r,k);
}
void bfs(int t){
  if(F[t]!=F[ch[t][0]]) fl[ch[t][0]]=1;
  if(F[t]!=F[ch[t][1]]) fl[ch[t][1]]=1;
  if(ch[t][0]) bfs(ch[t][0]);
  if(ch[t][1]) bfs(ch[t][1]);
}
void getans(int u){
  if(ch[u][0]) getans(ch[u][0]);
  if(ch[u][1]) getans(ch[u][1]);
  if(!ch[u][0]){
    dp[u][1]=dp[u][2]=1;
  }
  else{
    int l=ch[u][0],r=ch[u][1];
    // cerr<<u<<","<<l<<","<<r<<endl;
    //00
    //01
    //02
    dp[u][0]+=dp[l][0]*dp[r][2]+dp[l][2]*dp[r][0];
    //12
    dp[u][1]+=dp[l][1]*dp[r][2]+dp[l][2]*dp[r][1]+dp[l][1]*dp[r][1];
    //22
    dp[u][2]+=dp[l][2]*dp[r][2];
    dp[u][0]%=p;
    dp[u][1]%=p;
    dp[u][2]%=p;

    long long A=dp[u][0],B=dp[u][1],C=dp[u][2];
    // cerr<<A<<","<<B<<","<<C<<endl;
    dp[u][2]+=A+B+C;
    dp[u][0]%=p;
    dp[u][1]%=p;
    dp[u][2]%=p;
  }
  if(fl[u]){
    dp[u][0]=(dp[u][0]+dp[u][1])%p;
    dp[u][1]=0;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= n - 1; i++){
    cin >> X[i],X[i]++;
  }
  dfs(1,n,1);
  int l,r;
  while(m--){
    cin>>l>>r;
    l++;
    if(l==1&&r==n) fl[1]=1;
    vt[r].push_back(l),add(l,1);
  }
  for(int i=1;i<=n;i++){
    
    // cerr<<vw[i].size()<<"sdjlkajslk"<<endl;
    for(int j=0;j<vw[i].size();j++){
      int x=vw[i][j];
      // cerr<<x<<"sss"<<endl;
      // cout<<x<<","<<L[x]<<"query"<<endl;
      F[x]=query(L[x]);
    }
    for(int j=0;j<vt[i].size();j++) add(vt[i][j],-1);
  }
  bfs(1);
  getans(1);
  cout<<(dp[1][1]+dp[1][2])%p<<endl;
  // for(int i=1;i<=k;i++) cout<<L[i]<<","<<R[i]<<","<<fl[i]<<endl;
}
// 2 1
// 1
// 0 2

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 33848kb

input:

2 1
1
0 2

output:

result:

ok 1 number(s): "5"

Test #2:

score: 0

Accepted

time: 3ms

memory: 30964kb

input:

2 1
1
1 2

output:

result:

ok 1 number(s): "5"

Test #3:

score: 0

Accepted

time: 0ms

memory: 31052kb

input:

output:

result:

ok 1 number(s): "193"

Test #4:

score: 0

Accepted

time: 0ms

memory: 31648kb

input:

10 10
5 2 1 3 4 7 6 8 9
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10

output:

result:

ok 1 number(s): "70848"

Test #5:

score: 0

Accepted

time: 4ms

memory: 36088kb

input:

output:

result:

ok 1 number(s): "4"

Test #6:

score: 0

Accepted

time: 0ms

memory: 34664kb

input:

output:

result:

ok 1 number(s): "14"

Test #7:

score: 0

Accepted

time: 3ms

memory: 31148kb

input:

output:

result:

ok 1 number(s): "48"

Test #8:

score: 0

Accepted

time: 0ms

memory: 30864kb

input:

output:

result:

ok 1 number(s): "164"

Test #9:

score: 0

Accepted

time: 3ms

memory: 30996kb

input:

output:

result:

ok 1 number(s): "544"

Test #10:

score: 0

Accepted

time: 0ms

memory: 36592kb

input:

7 7
3 2 1 5 4 6
0 1
0 2
0 3
0 4
0 5
0 6
0 7

output:

result:

ok 1 number(s): "1856"

Test #11:

score: 0

Accepted

time: 4ms

memory: 36008kb

input:

8 8
3 1 2 4 7 5 6
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8

output:

result:

ok 1 number(s): "6528"

Test #12:

score: 0

Accepted

time: 0ms

memory: 31464kb

input:

9 9
3 1 2 4 7 6 5 8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9

output:

result:

ok 1 number(s): "21520"

Test #13:

score: 0

Accepted

time: 4ms

memory: 36232kb

input:

10 10
8 2 1 3 4 6 5 7 9
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10

output:

result:

ok 1 number(s): "71296"

Test #14:

score: 0

Accepted

time: 0ms

memory: 34728kb

input:

output:

result:

ok 1 number(s): "4"

Test #15:

score: 0

Accepted

time: 3ms

memory: 30952kb

input:

output:

result:

ok 1 number(s): "14"

Test #16:

score: 0

Accepted

time: 0ms

memory: 36640kb

input:

output:

result:

ok 1 number(s): "48"

Test #17:

score: 0

Accepted

time: 0ms

memory: 30980kb

input:

output:

result:

ok 1 number(s): "164"

Test #18:

score: 0

Accepted

time: 0ms

memory: 34720kb

input:

output:

result:

ok 1 number(s): "544"

Test #19:

score: 0

Accepted

time: 0ms

memory: 36328kb

input:

7 28
4 1 2 3 6 5
0 1
0 2
0 3
0 4
0 5
0 6
0 7
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7

output:

result:

ok 1 number(s): "1912"

Test #20:

score: 0

Accepted

time: 3ms

memory: 34752kb

input:

8 36
5 2 1 3 4 7 6
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8

output:

result:

ok 1 number(s): "6304"

Test #21:

score: 0

Accepted

time: 0ms

memory: 34756kb

input:

9 45
6 2 1 4 3 5 7 8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 6
4 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9

output:

result:

ok 1 number(s): "20736"

Test #22:

score: 0

Accepted

time: 0ms

memory: 31312kb

input:

10 55
6 3 2 1 4 5 8 7 9
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 5
4 6
4 7
4 8
4 9
4 10
5 6
5 7
5 8
5 9
5 10
6 7
6 8
6 9
6 10
7 8
7 9
7 10
8 9
8 10
9 10

output:

result:

ok 1 number(s): "70784"

Test #23:

score: 0

Accepted

time: 0ms

memory: 31172kb

input:

2 1
1
0 2

output:

result:

ok 1 number(s): "5"

Test #24:

score: 0

Accepted

time: 3ms

memory: 36088kb

input:

3 1
2 1
2 3

output:

result:

ok 1 number(s): "21"

Test #25:

score: 0

Accepted

time: 3ms

memory: 34600kb

input:

4 1
2 1 3
0 1

output:

result:

ok 1 number(s): "85"

Test #26:

score: 0

Accepted

time: 5ms

memory: 36468kb

input:

5 1
4 1 3 2
0 5

output:

result:

ok 1 number(s): "341"

Test #27:

score: -100

Wrong Answer

time: 3ms

memory: 31168kb

input:

6 1
5 1 2 3 4
0 2

output:

result:

wrong answer 1st numbers differ - expected: '1260', found: '1155'