Submission #904028

#	Time	Username	Problem	Language	Result	Execution time	Memory
904028		denniskim	Garden (JOI23_garden)	C++17	30 / 100	3081 ms	201048 KiB

garden

#include <bits/stdc++.h>

using namespace std;
typedef int 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 987654321
#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];
vector<ll> V;
ll P;

int main(void)
{
	fastio
	
	cin >> n >> m >> D;
	
	for(ll i = 1 ; i <= n ; ++i)
	{
		cin >> a[i].fi >> a[i].se;
		V.push_back(a[i].fi);
	}
	
	compress(V);
	
	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;
		priority_queue<ll> gap, egap;
		
		while(P < (ll)V.size() && V[P] < x)
			P++;
		
		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.push(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.push(R - vec[i].fi.se);
					else if(R == -1)
						gap.push(vec[i].fi.se - L);
					
					else
					{
						egap.push(R - L);
						gap.push(R - vec[i].fi.se);
						gap.push(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)
						egap.push(R - vec[i].fi.se);
					else if(R == -1)
						egap.push(vec[i].fi.se - L);
					
					else
					{
						gap.push(R - L);
						egap.push(R - vec[i].fi.se);
						egap.push(vec[i].fi.se - L);
					}
				}
			}
			
			if(vec[i].fi.fi != last)
				arr[x][last] = now;
			
			last = vec[i].fi.fi;
			
			while(!gap.empty() && !egap.empty() && gap.top() == egap.top())
				gap.pop(), egap.pop();
			
			if(gap.empty())
				now = 1;
			
			else
			{
				now = D - gap.top() + 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())
		{
			if(P == 0)
				S = max(S, V.back());
			else
				S = max(S, V[P - 1] + D);
		}
		
		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