oj.uz

Submission #820072

# Submission time Handle Problem Language Result Execution time Memory
820072 2023-08-10T18:48:18 Z YassirSalama Exam (eJOI20_exam) C++17
12 / 100
 33 ms 18004 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <functional>
#include <iterator>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=1e5+100;
const int LOGN=log2(MAXN+100)+1;
int st[MAXN+100][LOGN];
int a[MAXN];
void build(int n){
	for(int i=0;i<n;i++) st[i][0]=a[i];
		for(int j=1;j<LOGN;j++){
			for(int i=0;i+(1<<j)<=n;i++){
				st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
			}
	}
}
int query(int l,int r){
	int k=r-l+1;
	int kk=log2(k);
	return max(st[l][kk],st[r-(1<<kk)+1][kk]);
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n;
cin>>n;
int b[n];
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
memset(st,0,sizeof(st));
build(n);
vector<int> newarray(n,-1);
for(int i=0;i<n;i++){
	if(newarray[i]!=-1) continue;
	//If this element is the same as b[i]
	//then find max interval [left,right] such that i is in this interval and a[i] is the maximum there
	if(a[i]!=b[i]) continue;
	int l=0;
	int r=i;
	int mid;
	int ans=i;
	while(l<=r){
		mid=(l+r)/2;
		if(query(mid,i)==a[i]) ans=mid,r=mid-1;
		else l=mid+1;
	}
	l=i;
	r=n-1;
	mid=0;
	int ans2=i;
	while(l<=r){
		mid=(l+r)/2;
		if(query(i,mid)==a[i]) l=mid+1,ans2=mid;
		else r=mid-1;
	}
	for(int j=ans;j<=ans2;j++) newarray[j]=a[i];
	// dbg(ans,ans2,i,a[i],b[i]);
}
int ans=0;
for(int i=0;i<n;i++) {
	if(newarray[i]!=-1) ans++;
}
cout<<ans<<endl;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 13600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13652 KB Output is correct
2 Correct 9 ms 14488 KB Output is correct
3 Correct 20 ms 16744 KB Output is correct
4 Correct 20 ms 16360 KB Output is correct
5 Correct 27 ms 18004 KB Output is correct
6 Correct 33 ms 16340 KB Output is correct
7 Correct 21 ms 16512 KB Output is correct
8 Correct 30 ms 17864 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 13652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 13780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 13600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 13600 KB Output isn't correct
2 Halted 0 ms 0 KB -