Submission #820072

#	Time	Username	Problem	Language	Result	Execution time	Memory
820072		YassirSalama	Exam (eJOI20_exam)	C++17	12 / 100	33 ms	18004 KiB

exam

#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
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22