Submission #1239498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239498		ByeWorld	Garden (JOI23_garden)	C++20	60 / 100	3092 ms	39500 KiB

garden

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 5e5+10;
const int MAXA = 5e5+10;
const int SQRT = 450;
const ll INF = 2e12;
const int MOD = 998244353;
const int LOG = 30;
int sum(int a, int b){ return (a+MOD+b)%MOD; }
void chsum(int &a, int b){ a = sum(a,b); }
int mul(int a, int b){ return a*b%MOD; }
void chmul(int &a, int b){ a = mul(a,b); }
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
vector<int> dx = {0, 0, 1, -1};
vector<int> dy = {1, -1, 0, 0};

int n, m, d;
int x[MAXN], y[MAXN], a[MAXN], b[MAXN];
vector<pii> ins, vec[MAXN];
int nx[MAXN], ba[MAXN], idx[MAXN];

int calc(int x, int y){
	if(x < y) return ins[y].fi-ins[x].fi;
	return ins[y].fi+d-ins[x].fi;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	// ofstream deb("pp.txt");
	cin>>n>>m>>d;
	for(int i=1; i<=n; i++){
		cin>>x[i]>>y[i];
	}
	for(int i=1; i<=m; i++){
		cin>>a[i]>>b[i];
	}

	int ans = d*d;
	for(int le=0; le<=d-1; le++){
		// ri dipindahin ke kanan
		int r = le;
		for(int i=1; i<=n; i++){
			if(x[i] < le) chmx(r, x[i]+d);
			else chmx(r, x[i]);
			ins.pb({y[i], i});
		}
		// cerr << le << ' '<< ri << " ini yg n doang\n";

		for(int i=1; i<=m; i++){
			if((le <= a[i] && a[i] <= r) || (le <= a[i]+d && a[i]+d <= r));
			else {
				ins.pb({b[i], i+n}); 
				if(a[i] < le) vec[a[i]+d].pb({b[i], i+n});
				else vec[a[i]].pb({b[i], i+n});
			}
		}

		if(ins.size() == 0) assert(false);

		int mx = 0;
		sort(ins.begin(), ins.end());
		for(int i=0; i<ins.size(); i++)
			idx[ins[i].se] = i;
		for(int i=0; i+1<ins.size(); i++){
			nx[i] = i+1;
			chmx(mx, calc(i, i+1) );
		}
		nx[ (int)ins.size()-1 ] = 0;
		chmx(mx, calc((int)ins.size()-1, 0) );
 
		for(int i=1; i<ins.size(); i++)
			ba[i] = i-1;
		ba[0] = (int)ins.size()-1;

		for(auto [x, y] : ins)
			assert(x < d);

		for(int ri=r; ri<=le+d-1; ri++){
			for(auto [y, i] : vec[ri]){ // pop dari id
				int id = idx[i];
				int BA = ba[id], NX = nx[id];
				nx[BA] = NX; ba[NX] = BA;

				if(0<=BA&&BA<ins.size() && 0<=NX&&NX<ins.size()) ;
				else assert(false);
				chmx(mx, calc(BA, NX) );
			}
			// cerr << le << ' '<< ri << ' ' << mx << " mx\n";
			if(mx > d) assert(false);
				
				chmn(ans, (d-mx+1) * (ri-le+1) );
		}
		// cerr << "Line: " << __LINE__ << '\n';

		for(int i=0; i<=d+d+5; i++) vec[i].clear();
		ins.clear();
	}

	cout << ans << '\n';
		
} 

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