Submission #1199897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199897		midi	Exam (eJOI20_exam)	C++20	100 / 100	184 ms	22144 KiB

exam

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

typedef long long ll;
typedef long double ld;
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll, ll> prll;
typedef set<ll> setll;
typedef map<ll,ll> mapll;
#define uset unordered_set
typedef uset<ll> usetll;
#define umap unordered_map
typedef umap<ll,ll> umapll;

#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)

#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mp make_pair
#define fi first
#define se second
#define sz size
#define all(x) (x).begin(), (x).end()
#define all0(x, n) (x).begin(), (x).begin()+n
#define all1(x, n) (x).begin()+1, (x).begin()+n+1
#define allrev(x) (x).rbegin(), (x).rend()
#define in(v, s) ((s).find((v)) != (s).end())
#define GCD(x, y) __gcd(abs((x)), abs((y)))

#define INF (LLONG_MAX>>3ll)
#define MOD (1'000'000'007ll)

#define mxN (100'010ll)
#define lgN (17ll)
#define sgN (1ll<<17ll)

inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }

inline void print (vcll &a, ll n=-1, string name="")
{
	cout << name << ": ";
	if (n==-1) for (ll x:a) printf("%lli ", x);
	else
	{
		ll i;
		f0r(i,1,n) printf("%lli ", a[i]);
	}
	printf("\n");
}

ll n;
vcll a(mxN), b(mxN);
vc<vcll> arrows0(mxN);
vc<vcll> arrows1(mxN);

struct ST // range max queries
{
	vcll st;
	inline ST() { st.resize(sgN*2+10, 0); } 

	ll qry (ll it, ll lt, ll rt, ll l, ll r)
	{
		if (rt<=l or r<=lt) return 0;
		if (l<=lt and rt<=r) return st[it];
		ll i2=it*2, mt=(lt+rt)/2;
		return max(qry(i2,lt,mt,l,r), qry(i2+1,mt,rt,l,r));
	}
	inline ll qry (ll l, ll r) { return qry(1,0,n+1,l,r+1); }

	inline ll upd (ll it, ll lt, ll rt, ll j, ll x)
	{
		if (j<lt or rt<=j) return st[it];
		if (lt+1==rt) return st[it] = max(st[it],x);
		ll i2=it*2, mt=(lt+rt)/2;
		return st[it] = max(upd(i2,lt,mt,j,x), upd(i2+1,mt,rt,j,x));
	}
	inline void upd (ll j, ll x) { upd(1,0,n+1,j,x); }

} stg, dp0, dp1;

mapll lasti;

inline void bd_arrows()
{
	ll i;
	f0r(i,1,n) stg.upd(i,a[i]);

	f0r(i,1,n)
	{
		// if (in(b[i], lasti) and a[i]!=b[i])
		if (in(b[i], lasti))
		{
			ll j=lasti[b[i]];
			if (stg.qry(j,i) == a[j]) arrows0[i].pb(j);
		}
		lasti[a[i]]=i;
	}

	lasti.clear();
	r0f(i,n,1)
	{
		// printf("i: %lli, b[i]: %lli\n", i, b[i]);
		// if (in(b[i], lasti) and a[i]!=b[i])
		if (in(b[i], lasti))
		{
			ll j=lasti[b[i]];
			// printf("yes, j: %lli\n", j);
			if (stg.qry(i,j) == a[j]) arrows1[j].pb(i);
		}
		lasti[a[i]]=i;
		// printf("a[i] %lli\n", a[i]);
	}

	f0r(i,1,n) if (a[i]==b[i]) arrows1[i].pb(i);

	f0r(i,1,n) sort(all(arrows0[i]));
	f0r(i,1,n) sort(all(arrows1[i]));
}

inline void doq1 (ll i, ll j)
{
	ll x = dp1.qry(1,j-1) + 1;
	// printf("doq1(%lli, %lli): %lli\n", i, j, x);
	dp1.upd(j,x);
	dp0.upd(i,x);
}

inline void doq0 (ll i, ll j)
{
	ll x = dp0.qry(1,j) + 1;
	// printf("doq0(%lli, %lli): %lli\n", i, j, x);
	dp0.upd(j,x);
	dp1.upd(i,x);
}

inline void bd_dp()
{
	ll i;
	f0r(i,1,n)
	{
		for (ll j:arrows1[i]) doq1(i,j);
		for (ll j:arrows0[i]) doq0(i,j);
	}
}

inline void main2()
{
	scanf("%lli", &n);
	ll i;
	f0r(i,1,n) scanf("%lli", &a[i]);
	f0r(i,1,n) scanf("%lli", &b[i]);
	bd_arrows();
	bd_dp();
	printf("%lli\n", max(dp0.qry(1,n), dp1.qry(1,n)));
}

int main()
{
	// cin.tie(0); cout.tie(0);
	// ios_base::sync_with_stdio(0);
	srand(time(0));

	// freopen("file.in", "r", stdin);

	ll t=1;
	// scanf("%lli", &t);
	while (t--) main2();

	return 0;
}

Compilation message (stderr)

exam.cpp: In function 'void main2()':
exam.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         scanf("%lli", &n);
      |         ~~~~~^~~~~~~~~~~~
exam.cpp:157:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         f0r(i,1,n) scanf("%lli", &a[i]);
      |                    ~~~~~^~~~~~~~~~~~~~~
exam.cpp:158:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         f0r(i,1,n) scanf("%lli", &b[i]);
      |                    ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22