QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#218737 | #7147. IQ Test | SolitaryDream# | WA | 1ms | 9184kb | C++17 | 2.0kb | 2023-10-18 17:47:37 | 2023-10-18 17:47:38 |
Judging History
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),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));
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: 0ms
memory: 7636kb
input:
2 A 0 1 B 0 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7988kb
input:
2 A 1 2 B 0 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 8744kb
input:
1 A 1 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 9184kb
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:
7
result:
wrong answer 1st numbers differ - expected: '5', found: '7'