Submission #904022

#	Time	Username	Problem	Language	Result	Execution time	Memory
904022		denniskim	Garden (JOI23_garden)	C++17	30 / 100	3041 ms	351024 KiB

garden

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n, m, D;
pll a[500010], b[500010];
vector<ll> A[5010], B[5010];
ll arr[5010][10010];
set<ll> V;

int main(void)
{
	fastio
	
	cin >> n >> m >> D;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		cin >> a[i].fi >> a[i].se;
		V.insert(a[i].fi);
	}
	
	for(ll i = 1 ; i <= m ; i++)
		cin >> b[i].fi >> b[i].se;
	
	for(ll i = 1 ; i <= n ; i++)
		A[a[i].se].push_back(a[i].fi);
	
	for(ll i = 1 ; i <= m ; i++)
		B[b[i].se].push_back(b[i].fi);
	
	for(ll i = 0 ; i < D ; i++)
	{
		compress(A[i]);
		compress(B[i]);
	}
	
	ll ans = INF;
	
	for(ll x = 0 ; x < D ; x++)
	{
		vector< pair<pll, ll> > vec;
		vector<ll> vv;
		multiset<ll> st, gap;
		
		while(!V.empty() && (*V.begin()) < x)
		{
			ll gapp = (*V.begin());
			V.erase(gapp);
			V.insert(gapp + D);
		}
		
		for(ll i = 0 ; i < D ; i++)
		{
			ll l = 0, r = (ll)A[i].size() - 1;
			
			while(l <= r)
			{
				ll mid = (l + r) >> 1;
				
				if(A[i][mid] >= x)
					r = mid - 1;
				else
					l = mid + 1;
			}
			
			if(!A[i].empty())
			{
				if(l < (ll)A[i].size())
					vec.push_back({{A[i][l], i}, 1});
				else
					vec.push_back({{A[i][0] + D, i}, 1});
			}
			
			if(B[i].empty())
				continue;
			
			vv.push_back(i);
			l = 0, r = (ll)B[i].size() - 1;
			
			while(l <= r)
			{
				ll mid = (l + r) >> 1;
				
				if(B[i][mid] >= x)
					r = mid - 1;
				else
					l = mid + 1;
			}
			
			if(r == -1)
				vec.push_back({{B[i].back(), i}, 2});
			else
				vec.push_back({{B[i][r] + D, i}, 2});
		}
		
		ll siz = 0;
		ll last = x, now = INF;
		ll S = x;
		
		compress(vv);
		siz = (ll)vv.size();
		
		for(ll i = 0 ; i < siz ; i++)
		{
			st.insert(vv[i]);
			
			if(i >= 1)
			{
				gap.insert(vv[i] - vv[i - 1]);
				now = min(now, D - vv[i] + vv[i - 1] + 1);
			}
		}
		
		sort(vec.begin(), vec.end());
		siz = (ll)vec.size();
		
		for(ll i = 0 ; i < siz ; i++)
		{
			if(vec[i].se == 1)
			{
				S = max(S, vec[i].fi.fi);
				
				auto p = st.lower_bound(vec[i].fi.se);
				ll L = -1, R = -1;
				
				if(p != st.end())
					R = (*p);
				
				if(p != st.begin())
				{
					p--;
					L = (*p);
				}
				
				st.insert(vec[i].fi.se);
				
				if(L != -1 || R != -1)
				{
					if(L == -1)
						gap.insert(R - vec[i].fi.se);
					else if(R == -1)
						gap.insert(vec[i].fi.se - L);
					
					else
					{
						gap.erase(gap.find(R - L));
						gap.insert(R - vec[i].fi.se);
						gap.insert(vec[i].fi.se - L);
					}
				}
			}
			
			else
			{
				auto p = st.lower_bound(vec[i].fi.se);
				ll L = -1, R = -1;
				
				p++;
				
				if(p != st.end())
					R = (*p);
				
				p--;
				
				if(p != st.begin())
				{
					p--;
					L = (*p);
				}
				
				st.erase(st.find(vec[i].fi.se));
				
				if(L != -1 || R != -1)
				{
					if(L == -1)
						gap.erase(gap.find(R - vec[i].fi.se));
					else if(R == -1)
						gap.erase(gap.find(vec[i].fi.se - L));
					
					else
					{
						gap.insert(R - L);
						gap.erase(gap.find(R - vec[i].fi.se));
						gap.erase(gap.find(vec[i].fi.se - L));
					}
				}
			}
			
			if(vec[i].fi.fi != last)
				arr[x][last] = now;
			
			last = vec[i].fi.fi;
			
			if(gap.empty())
				now = 1;
			
			else
			{
				now = D - (*gap.rbegin()) + 1;
				
				if(!st.empty())
					now = min(now, (*st.rbegin()) - (*st.begin()) + 1);
			}
		}
		
		arr[x][last] = now;
		
		for(ll i = x ; i < D * 2 ; i++)
		{
			if(arr[x][i])
				continue;
			
			arr[x][i] = arr[x][i - 1];
		}
		
		if(!V.empty())
			S = max(S, (*V.rbegin()));
		
		for(ll j = S ; j < D * 2 ; j++)
		{
			if(arr[x][j] != INF)
				ans = min(ans, (j - x + 1) * arr[x][j]);
		}
	}
	
	cout << ans;
	return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25