#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll INF=1e9+9;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
ll seg[400005]={0};
void update(ll s,ll e,ll qs,ll qe,ll idx,ll k)
{
if(s==e&&s==qs)
{
seg[idx]=max(seg[idx],k);
return;
}
if(qs>e||qe<s)
return;
ll mid=(s+e)/2;
update(s,mid,qs,qe,idx*2,k);
update(mid+1,e,qs,qe,idx*2+1,k);
seg[idx]=max(seg[idx*2],seg[idx*2+1]);
}
ll query(ll s,ll e,ll qs,ll qe,ll idx)
{
if(qs<=s&&e<=qe)
return seg[idx];
if(qs>e||qe<s)
return 0;
ll mid=(s+e)/2;
ll a=query(s,mid,qs,qe,idx*2);
ll b=query(mid+1,e,qs,qe,idx*2+1);
return max(a,b);
}
const int N = 5011;
int a[N],b[N];
int dp[N][N];
int mx[N][N];
vector<int> vv;
int c;
map<int,int> mt;
int amount[N*5];
void subtask1356(vector<int> &v,int n,int a[],int b[])
{
sort(vv.begin(),vv.end());
for (int i=0; i<vv.size(); i++)
{
if(mt[vv[i]]==0)
{
++c;
mt[vv[i]]=c;
}
}
for(int i=1; i<=n; i++)
a[i]=mt[a[i]];
for(int i=1; i<=n; i++)
b[i]=mt[b[i]];
for(int i=0; i<=n; i++)
for(int j=i; j<=n; j++)
mx[i][j]=max(mx[i][j-1],a[j]);
dp[1][1]=0;
if(a[1]==b[1])
dp[1][1]=1;
for(int j=1; j<=n; j++)
{
for(int i=1; i<=c; i++)
amount[i]=0;
for(int i=j; i<=n; i++)
{
if(i==j)
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+(a[i]==b[i]));
++amount[b[i]];
if(i+1<=n)
{
if(a[i+1]<=mx[j][i])
{
if(b[i+1]==mx[j][i])
dp[i+1][j]=max(dp[i+1][j],dp[i][j]+1);
else
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
}
else
{
dp[i+1][j]=max(dp[i+1][j],
dp[i][j]-amount[mx[j][i]]+amount[mx[j][i+1]]+(b[i+1]==a[i+1]));
}
}
if(j+1<=i)
dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
}
}
cout<<dp[n][n];
cout<<"\n";
}
void subtask4(int n,int a[],int b[])
{
map<ll,ll>pos;
for(ll i=0;i <n; i++)
pos[a[i]] = i+1;
for(ll i=0; i<n; i++)
{
b[i] = pos[b[i]];
if(b[i] == 0)
b[i] = INF;
}
ll l[n],r[n];
priority_queue<ii,vector<ii>,greater<ii> >pq;
for(ll i=0;i <n; i++)
{
pq.push(ii(a[i],i));
while(pq.top().F < a[i])
{
r[pq.top().S] = i-1;
pq.pop();
}
}
while(!pq.empty())
{
r[pq.top().S] = n-1;
pq.pop();
}
for(ll i=n-1; i>=0;i--)
{
pq.push(ii(a[i],i));
while(pq.top().F < a[i])
{
l[pq.top().S] = i+1;
pq.pop();
}
}
while(!pq.empty())
{
l[pq.top().S] = 0;
pq.pop();
}
ll ans = 0;
ll dp1[n+1];
dp1[0] = 0;
for(ll i=1; i<n+1; i++)
{
dp1[i] = 0;
if(b[i-1] == INF || !(l[b[i-1]-1] <= i-1 && i-1 <= r[b[i-1]-1]))
continue;
dp1[i] = query(1,n+1,1,b[i-1],1) + 1;
update(1,n+1,b[i-1],b[i-1],1,dp1[i]);
ans = max(ans,dp1[i]);
}
cout<<ans<<endl;
}
void subtask2(int n,int a[],int b[])
{
vector<int>vx;
for(int i=0; i<n; ++i)
{
if(a[i]==b[0])
vx.push_back(i);
}
int sm(0);
map<int,int>v;
for(auto i:vx)
{
int j(i);
if(!v[j])
{
while(j>=0&&b[0]<=a[j])
{
v[j]=1;
--j;
}
sm+=i-j;
j=i;
while(j<n&&b[0]<=a[j])
{
v[j]=1;
++j;
}
--j;
sm+=j-i;
}
}
cout<<sm<<"\n";
}
bool is(int n,int a[],int b[])
{
if(n<=5000)
return true;
return false;
}
bool is1(int n,int a[],int b[])
{
for(int i=0; i<n; ++i)
{
if(b[i]!=b[0])
return false;
}
return true;
}
bool is2(int n,int a[],int b[])
{
set<int>ss;
for(int i=0; i<n; ++i)
ss.insert(a[i]);
if(ss.size()==n)
return true;
return false;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
a[i]*=-1;
vv.push_back(a[i]);
}
for(int i=1; i<=n; i++)
{
cin>>b[i];
b[i]*=-1;
vv.push_back(b[i]);
}
if(is(n,a,b))
subtask1356(vv,n,a,b);
else if(is1(n,a,b))
subtask2(n,a,b);
else if(is2(n,a,b))
subtask4(n,a,b);
}
}
Compilation message
exam.cpp: In function 'void subtask1356(std::vector<int>&, int, int*, int*)':
exam.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i=0; i<vv.size(); i++)
| ~^~~~~~~~~~
exam.cpp: In function 'bool is2(int, int*, int*)':
exam.cpp:206:13: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
206 | if(ss.size()==n)
| ~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
7132 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
7132 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
7132 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
