Submission #1362228

#TimeUsernameProblemLanguageResultExecution timeMemory
1362228weedywelonGrid Coloring (JOI25_ho_t1)C++20
100 / 100
217 ms34888 KiB
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;

const LL MAXN=2e5+5;
map<LL,LL> cnt;
LL a[MAXN], b[MAXN];

signed main(){
	FAST;
	LL n; cin>>n;
	
	vector<LL> v1,val1,v2,val2;
	LL cur=0;
	FR(i,1,n+1){
		cin>>a[i];
		if (a[i]>cur && i>1){
			v1.push_back(i);
			cur=a[i];
		}
		val1.push_back(cur);
		cnt[a[i]]++;
	}
	
	cur=0;
	FR(i,1,n+1){
		cin>>b[i];
		if (b[i]>cur && i>1){
			v2.push_back(i);
			cur=b[i];
		}
		val2.push_back(cur);
		if (i>1) cnt[b[i]]++;
	}
	
	v1.push_back(n+1);
	val1.push_back(1e9+1);
	v2.push_back(n+1);
	val2.push_back(1e9+1);
	
	/*for (LL x:val1) cout<<x<<" ";
	cout<<"\n";
	for (LL x:val2) cout<<x<<" ";
	cout<<"\n";*/

	FOR(i,SZ(v1)-1){
		LL x=a[v1[i]];
		LL len=v1[i+1]-v1[i];
		LL len2=upper_bound(val2.begin(),val2.end(),x)-val2.begin();
		cnt[x]+=len*(len2-1);
		
		//cout<<x<<": "<<len<<" "<<(len2-1)<<"\n";
	}
	
	FOR(i,SZ(v2)-1){
		LL x=b[v2[i]];
		LL len=v2[i+1]-v2[i];
		LL len2=lower_bound(val1.begin(),val1.end(),x)-val1.begin();
		cnt[x]+=len*(len2-1);
		
		//cout<<x<<": "<<len<<" "<<(len2-1)<<"\n";
	}
	
	LL c=0, mx=0;
	for (PLL p:cnt){
		if (p.B>mx){
			c=p.A;
			mx=p.B;
		}
		else if (p.B==mx) c=max(c,p.A);
	}
	cout<<c<<" "<<mx;
	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...