제출 #1331744

#제출 시각아이디문제언어결과실행 시간메모리
1331744nminhnguyenleGrid Coloring (JOI25_ho_t1)C++20
100 / 100
534 ms47404 KiB
// NAM MÔ A DI ĐÀ PHẬT

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3","unroll-loops")

// defines
#define int long long
#define inf LLONG_MAX/20
#define fastio() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define fr front
#define bk back
#define fi first
#define se second

// typedefs
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pi;
typedef pair<string, ll> psi;
typedef pair<ll, pi> pii;
typedef pair<pi, pi> piii;

signed main(){
    fastio();
    int n;
    cin>>n;
    vector<int> a(n+1),b(n+1);
    a[0]=0;
    b[0]=0;
    map<int,int> mp;
    for(int i=1;i<=n;i++){
		cin>>a[i];
		mp[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
		mp[b[i]]++;
	}
	mp[b[1]]--; // double counting
	for(int i=3;i<=n;i++){
		a[i]=max(a[i-1],a[i]);
		b[i]=max(b[i-1],b[i]);
	}
	set<int> st;
	for(int i=2;i<=n;i++){
		st.insert(a[i]);
	}
	for(int i=2;i<=n;i++){
		st.insert(b[i]);
	}
	int prev=0;
	for(auto it:st){
		int r=upper_bound(a.begin()+2,a.end(),it)-a.begin()-2;
		int c=upper_bound(b.begin()+2,b.end(),it)-b.begin()-2;
		int area=r*c;
		int temp=area-prev;
		mp[it]+=temp;
		prev=area;
	}
	int maxc=0; // color
	int maxf=0; // cnt
	for(auto [c,frq]:mp){
		if(frq>maxf){
			maxf=frq;
			maxc=c;
		}
		if(frq==maxf){
			maxc=max(c,maxc);
		}
	}
	cout<<maxc<<" "<<maxf;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...