제출 #1366044

#제출 시각아이디문제언어결과실행 시간메모리
1366044blopGrid Coloring (JOI25_ho_t1)C++20
100 / 100
263 ms31748 KiB
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template<class T>
using ordered_set = tree<T, null_type, less<T>, 
					rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U>
using ordered_map = tree<T, U, less<T>, rb_tree_tag,
					tree_order_statistics_node_update>;
#define ll long long
#define ld long double
#define MOD 998244353
#define MAXN 250000
#define SIZE 100
#define pb push_back

ll power(ll a, ll b){
	if (b == 0) return 1;
	ll res = power(a, b / 2);
	if (b % 2 == 1) return res * res % MOD * a % MOD;
	return res * res % MOD;
	
//	if (b % 2 == 1) return res * res * a;
//	return res * res;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin >> n;
	vector<int> a(n + 1), b(n + 1);
	int row = n, col = n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	vector<tuple<int, int, int>> all;
	map<int, ll> cnt;
	for (int i = 1; i <= n; i++){
		cnt[a[i]]++;
		if (i != 1){
			cnt[b[i]]++;
		}
		else continue;
		all.pb({a[i], 1, i});
		all.pb({b[i], 2, i});
	}
	sort(all.begin(), all.end(), greater<tuple<int, int, int>>());
	for (auto [val, type, pos] : all){
		if (type == 1){
			cnt[val] += (ll)max(0, row - pos + 1) * (col - 1);
//			cout << val << ", " << type << ", " << pos << ": " << (ll)max(0, row - pos + 1) * (col - 1) << "\n";
			row = min(row, pos - 1);
		}
		else{
			cnt[val] += (ll)max(0, col - pos + 1) * (row - 1);
//			cout << val << ", " << type << ", " << pos << ": " << (ll)max(0, col - pos + 1) * (row - 1) << "\n";
			col = min(col, pos - 1);
			
		}
	}
	ll ansVal = -1, ansCnt = 0;
	for (auto &p : cnt){
		if (p.second >= ansCnt){
			ansCnt = p.second;
			ansVal = p.first;
		}
	}
	cout << ansVal << " " << ansCnt << "\n";
	
	
	return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…