#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p (a, b, (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p (a, b, (__typeof__ ((a) + (b))) 0)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
//Note to self: Check for overflow
int n,bans;
vector<int> a,b;
set<vector<int>> setcina;
int calc(vector<int> niz)
{
int cnt=0;
ff(i,0,n)cnt+=(niz[i]==b[i]?1:0);
return cnt;
}
void brutuj(vector<int> niz)
{
if (setcina.find(niz)!=setcina.end())return;
setcina.insert(niz);
bans=max(bans,calc(niz));
ff(l,0,n)
{
int mx=niz[l];
ff(r,l+1,n)
{
mx=max(mx,niz[r]);
auto novi=niz;
fff(i,l,r)novi[i]=mx;
brutuj(novi);
}
}
}
bool sub4(vector<int> niz)
{
set<int> s;
for(int i:niz)s.insert(i);
return s.size()==niz.size();
}
int mx[400005];
void Set(int node,int l,int r,int x,int y)
{
if(l==r)
{
mx[node]=y;
return;
}
int mid=(l+r)/2;
if(x<=mid)Set(node*2,l,mid,x,y);
else Set(node*2+1,mid+1,r,x,y);
mx[node]=max(mx[node*2],mx[node*2+1]);
}
int Get(int node,int l,int r,int ll,int rr)
{
if(l>r||l>rr||r<ll)return 0;
if(ll<=l&&r<=rr)return mx[node];
int mid=(l+r)/2;
return max(Get(node*2,l,mid,ll,rr),Get(node*2+1,mid+1,r,ll,rr));
}
int main()
{
FAST;
cin>>n;
a.resize(n),b.resize(n);
ff(i,0,n) cin>>a[i];
ff(i,0,n) cin>>b[i];
if(n<=10)
{
brutuj(a);
cout<<bans;
return 0;
}
if(*min_element(all(b))==*max_element(all(b)))
{
ff(i,0,n)
{
if(a[i]==b[i])
{
bff(j,0,i)
{
if(a[j]>=a[i])break;
a[j]=a[i];
}
ff(j,i+1,n)
{
if(a[j]>=a[i])break;
a[j]=a[i];
}
}
}
cout<<calc(a);
return 0;
}
if(false && n<=5000)
{
ff(i,0,n)
{
pii x={calc(a),i};
int bal=calc(a);
bff(j,0,i)
{
if(a[j]==b[j])bal--;
if(a[i]==b[j])bal++;
x=max(x,mp(bal,j));
}
fff(j,x.second,i)a[j]=a[i];
assert(calc(a));
}
cout<<calc(a);
return 0;
}
if(sub4(a))
{
map<int,int> mp;
ff(i,0,n)mp[a[i]]=i;
ff(i,0,n)b[i]=mp[b[i]];
ff(i,0,n)
{
int cur=Get(1,0,n-1,0,b[i]);
Set(1,0,n-1,b[i],cur);
}
cout<<mx[1];
return 0;
}
}
//Note to self: Check for overflow
Compilation message
exam.cpp: In function 'int calc(std::vector<int>)':
exam.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
| ^
exam.cpp:53:5: note: in expansion of macro 'ff'
53 | ff(i,0,n)cnt+=(niz[i]==b[i]?1:0);
| ^~
exam.cpp: In function 'void brutuj(std::vector<int>)':
exam.cpp:15:28: warning: unnecessary parentheses in declaration of 'l' [-Wparentheses]
15 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
| ^
exam.cpp:62:5: note: in expansion of macro 'ff'
62 | ff(l,0,n)
| ^~
exam.cpp:15:28: warning: unnecessary parentheses in declaration of 'r' [-Wparentheses]
15 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
| ^
exam.cpp:65:9: note: in expansion of macro 'ff'
65 | ff(r,l+1,n)
| ^~
exam.cpp:16:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
16 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
| ^
exam.cpp:69:13: note: in expansion of macro 'fff'
69 | fff(i,l,r)novi[i]=mx;
| ^~~
exam.cpp: In function 'int main()':
exam.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
| ^
exam.cpp:110:5: note: in expansion of macro 'ff'
110 | ff(i,0,n) cin>>a[i];
| ^~
exam.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
| ^
exam.cpp:111:5: note: in expansion of macro 'ff'
111 | ff(i,0,n) cin>>b[i];
| ^~
exam.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
| ^
exam.cpp:122:9: note: in expansion of macro 'ff'
122 | ff(i,0,n)
| ^~
exam.cpp:17:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
17 | #define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
| ^
exam.cpp:126:17: note: in expansion of macro 'bff'
126 | bff(j,0,i)
| ^~~
exam.cpp:15:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
15 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
| ^
exam.cpp:131:17: note: in expansion of macro 'ff'
131 | ff(j,i+1,n)
| ^~
exam.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
| ^
exam.cpp:144:9: note: in expansion of macro 'ff'
144 | ff(i,0,n)
| ^~
exam.cpp:17:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
17 | #define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
| ^
exam.cpp:148:13: note: in expansion of macro 'bff'
148 | bff(j,0,i)
| ^~~
exam.cpp:16:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
16 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
| ^
exam.cpp:154:13: note: in expansion of macro 'fff'
154 | fff(j,x.second,i)a[j]=a[i];
| ^~~
exam.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
| ^
exam.cpp:164:9: note: in expansion of macro 'ff'
164 | ff(i,0,n)mp[a[i]]=i;
| ^~
exam.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
| ^
exam.cpp:165:9: note: in expansion of macro 'ff'
165 | ff(i,0,n)b[i]=mp[b[i]];
| ^~
exam.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
| ^
exam.cpp:167:9: note: in expansion of macro 'ff'
167 | ff(i,0,n)
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| 6 |
Correct |
227 ms |
2032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
6 ms |
460 KB |
Output is correct |
| 3 |
Correct |
19 ms |
1288 KB |
Output is correct |
| 4 |
Correct |
15 ms |
1504 KB |
Output is correct |
| 5 |
Correct |
29 ms |
1484 KB |
Output is correct |
| 6 |
Correct |
16 ms |
1508 KB |
Output is correct |
| 7 |
Correct |
16 ms |
1484 KB |
Output is correct |
| 8 |
Correct |
26 ms |
1364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| 6 |
Correct |
227 ms |
2032 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| 6 |
Correct |
227 ms |
2032 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
