QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#218762#7147. IQ TestSolitaryDream#WA 1ms8680kbC++172.0kb2023-10-18 18:06:592023-10-18 18:07:00

Judging History

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

  • [2023-10-18 18:07:00]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8680kb
  • [2023-10-18 18:06:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;

const int N=4e5+1e3+7;

int n,w[N][2];

int f[N][2];

struct BIT {
    int c[N];

    vector<pair<int*,int> >mod; 

    void clr(int x)
    {
        x+=N/2;
        while(x<N)
        {
            c[x]=-1e9;
            x+=x&-x;
        }
    }

    void add(int x,int v)
    {
        x+=N/2;
        while(x<N)
        {
            c[x]=max(c[x],v);
            x+=x&-x;
        }
    }

    int qry(int x)
    {
        x+=N/2;
        int ret=-1e9;
        while(x)
        {
            ret=max(ret,c[x]);
            x-=x&-x;
        }
        return ret;
    }
}T;

int ans=0;

void solve(int l,int r)
{
    if(l==r)
    {
        for(int j=0;j<2;j++)
        {
            if(w[l][j]>=0&&w[l][j]<=l-1)
                f[l][j]=max(f[l][j],1);
            ans=max(ans,f[l][j]);
        }
        return;
    }
    int mid=(l+r)>>1;
    solve(l,mid);
    vector<pii> v;
    for(int i=l;i<=r;i++)
        for(int j=0;j<2;j++)
            v.push_back({i,j});
    sort(v.begin(),v.end(),[&](const pii &a,const pii &b) {
        if(w[a.first][a.second]!=w[b.first][b.second])
            return w[a.first][a.second]<w[b.first][b.second];
        return a.first<b.first;
    });
    for(auto [p,s]:v)
    {
        if(p<=mid)
            T.add(p-w[p][s]-(s==0)+1,f[p][s]);
        else
        {
            if(w[p][s]>=0&&w[p][s]<=p-1)
                f[p][s]=max(f[p][s],T.qry(p-w[p][s])+1);
        }
    }
    for(auto [p,s]:v)
        if(p<=mid)
            T.clr(p-w[p][s]-(s==0)+1);
    solve(mid+1,r);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        char ty[3];
        scanf("%s",ty);
        scanf("%d%d",&w[i][0],&w[i][1]);
        if(ty[0]=='B')
        {
            for(int j=0;j<2;j++)
                w[i][j]=i-1-w[i][j];
        }
        f[i][0]=f[i][1]=-1e9;
    }
    fill(T.c,T.c+N,-1e9);
    solve(1,n);
    printf("%d\n",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7980kb

input:

2
A 0 1
B 0 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 8632kb

input:

2
A 1 2
B 0 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 7416kb

input:

1
A 1 1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 1ms
memory: 8680kb

input:

10
A 1 1
A 1 0
B 1 0
B 3 1
B 1 0
B 1 5
A 5 6
B 3 0
A 0 0
B 8 9

output:

5

result:

ok 1 number(s): "5"

Test #5:

score: 0
Accepted
time: 1ms
memory: 7416kb

input:

10
A 3 0
B 0 1
B 0 2
A 1 5
B 5 2
B 3 2
B 7 2
A 4 3
B 6 0
B 2 2

output:

6

result:

ok 1 number(s): "6"

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 8304kb

input:

10
B 1 0
A 0 0
A 1 4
A 4 1
B 0 2
A 5 1
B 5 0
B 3 2
A 2 1
A 6 7

output:

7

result:

wrong answer 1st numbers differ - expected: '6', found: '7'