oj.uz

Submission #512609

# Submission time Handle Problem Language Result Execution time Memory
512609 2022-01-16T13:48:26 Z new_acc Exam (eJOI20_exam) C++14
100 / 100
 148 ms 12432 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(ll a = 0; a < (b); a++)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const int SS=1<<19;
int a[N],b[N],seg[SS*2+10];
pair<int,int> naj[N];
void Insert(int a,int ind){
	for(ind+=SS;ind>0;ind>>=1) seg[ind]=max(seg[ind],a);
}
int Query(int pocz,int kon){
	int res=0;
	for(pocz+=SS-1,kon+=SS+1;(pocz>>1)!=(kon>>1);pocz>>=1,kon>>=1){
		if(!(pocz&1)) res=max(res,seg[pocz+1]);
		if(kon&1) res=max(res,seg[kon-1]);
	}
	return res;
}
unordered_map<int,int>m;
void solve(){
	int n;
	cin>>n;
	rep(i,n) cin>>a[i];
	rep(i,n) cin>>b[i];
	rep(i,n) Insert(a[i],i);
	rep(i,n){
		m[a[i]]=i;
		if(m.count(b[i])>0 and Query(m[b[i]],i)==b[i]) naj[i].fi=m[b[i]];
		else naj[i].fi=-1;
	}
	m.clear();
	for(int i=n-1;i>=0;i--){
		m[a[i]]=i;
		if(m.count(b[i])>0 and Query(i,m[b[i]])==b[i]) naj[i].se=m[b[i]];
		else naj[i].se=-1;
	}
	rep(i,SS*2+10) seg[i]=0;
	rep(i,n){
		int g=0,g2=0;
		if(naj[i].fi!=-1) g=Query(0,naj[i].fi);
		if(naj[i].se!=-1) g2=Query(0,naj[i].se);
		if(naj[i].fi!=-1) Insert(g+1,naj[i].fi);
		if(naj[i].se!=-1) Insert(g2+1,naj[i].se);

	}
	cout<<Query(0,n)<<"\n";
}
int main(){
	solve();
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4396 KB Output is correct
2 Correct 2 ms 4392 KB Output is correct
3 Correct 2 ms 4304 KB Output is correct
4 Correct 2 ms 4304 KB Output is correct
5 Correct 2 ms 4304 KB Output is correct
6 Correct 2 ms 4304 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4428 KB Output is correct
2 Correct 22 ms 5016 KB Output is correct
3 Correct 67 ms 11036 KB Output is correct
4 Correct 55 ms 6224 KB Output is correct
5 Correct 112 ms 12432 KB Output is correct
6 Correct 47 ms 6328 KB Output is correct
7 Correct 53 ms 6428 KB Output is correct
8 Correct 102 ms 10584 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4300 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 4 ms 4560 KB Output is correct
4 Correct 6 ms 4668 KB Output is correct
5 Correct 7 ms 4692 KB Output is correct
6 Correct 8 ms 4664 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4684 KB Output is correct
2 Correct 51 ms 7372 KB Output is correct
3 Correct 105 ms 11500 KB Output is correct
4 Correct 148 ms 12288 KB Output is correct
5 Correct 135 ms 12328 KB Output is correct
6 Correct 99 ms 11560 KB Output is correct
7 Correct 127 ms 12320 KB Output is correct
8 Correct 88 ms 11564 KB Output is correct
9 Correct 97 ms 11644 KB Output is correct
10 Correct 86 ms 11484 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4396 KB Output is correct
2 Correct 2 ms 4392 KB Output is correct
3 Correct 2 ms 4304 KB Output is correct
4 Correct 2 ms 4304 KB Output is correct
5 Correct 2 ms 4304 KB Output is correct
6 Correct 2 ms 4304 KB Output is correct
7 Correct 2 ms 4304 KB Output is correct
8 Correct 2 ms 4304 KB Output is correct
9 Correct 2 ms 4304 KB Output is correct
10 Correct 2 ms 4304 KB Output is correct
11 Correct 2 ms 4304 KB Output is correct
12 Correct 2 ms 4304 KB Output is correct
13 Correct 2 ms 4432 KB Output is correct
14 Correct 2 ms 4304 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4396 KB Output is correct
2 Correct 2 ms 4392 KB Output is correct
3 Correct 2 ms 4304 KB Output is correct
4 Correct 2 ms 4304 KB Output is correct
5 Correct 2 ms 4304 KB Output is correct
6 Correct 2 ms 4304 KB Output is correct
7 Correct 2 ms 4300 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 4 ms 4560 KB Output is correct
10 Correct 6 ms 4668 KB Output is correct
11 Correct 7 ms 4692 KB Output is correct
12 Correct 8 ms 4664 KB Output is correct
13 Correct 2 ms 4304 KB Output is correct
14 Correct 2 ms 4304 KB Output is correct
15 Correct 2 ms 4304 KB Output is correct
16 Correct 2 ms 4304 KB Output is correct
17 Correct 2 ms 4304 KB Output is correct
18 Correct 2 ms 4304 KB Output is correct
19 Correct 2 ms 4432 KB Output is correct
20 Correct 2 ms 4304 KB Output is correct
21 Correct 2 ms 4404 KB Output is correct
22 Correct 3 ms 4432 KB Output is correct
23 Correct 8 ms 4560 KB Output is correct
24 Correct 6 ms 4560 KB Output is correct
25 Correct 7 ms 4484 KB Output is correct
26 Correct 5 ms 4536 KB Output is correct
27 Correct 5 ms 4432 KB Output is correct
28 Correct 7 ms 4688 KB Output is correct
29 Correct 5 ms 4688 KB Output is correct
30 Correct 7 ms 4636 KB Output is correct
31 Correct 7 ms 4656 KB Output is correct
32 Correct 7 ms 4644 KB Output is correct