Submission #828388

#	Time	Username	Problem	Language	Result	Execution time	Memory
828388		jamezzz	Garden (JOI23_garden)	C++17	100 / 100	891 ms	14500 KiB

garden

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define psf push_front
#define ppb pop_back
#define ppf pop_front
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar_unlocked();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 5005

int n,m,d;
vi lasts[maxn*2];
int mx;
vi l,r,v,num;

void reset(){
	mx=0;
	l.clear();
	r.clear();
	v.clear();
	num.clear();
	l.resize(d,0);
	r.resize(d,0);
	v.resize(d,0);
	num.resize(d,0);
}

void on(int i){
	if(v[i]==1)return;
	int pv=((i==0)?d-1:i-1);
	int nx=((i==d-1)?0:i+1);
	int L=(v[pv]==1?l[pv]:i);
	int R=(v[nx]==1?r[nx]:i);
	if(L==nx)mx=d;
	else{
		int nw=num[L]+num[R]+1;
		mx=max(mx,nw);
		num[L]=num[R]=nw;
		l[R]=L;
		r[L]=R;
		v[i]=1;
	}
}

int get(){
	return mx;
}

int main(){
	sf("%d%d%d",&n,&m,&d);
	vector<bool> xmust(d),ymust(d);
	for(int i=0;i<n;++i){
		int x,y;sf("%d%d",&x,&y);
		xmust[x]=ymust[y]=true;
	}
	vector<vi> b(d);
	for(int i=0;i<m;++i){
		int x,y;sf("%d%d",&x,&y);
		if(xmust[x]||ymust[y])continue;
		b[x].pb(y);
	}
	for(int i=0;i<d;++i){
		xmust.pb(xmust[i]);
		b.pb(b[i]);
	}
	
	//calculate answer if we take all x's
	reset();
	for(int i=0;i<d;++i){
		if(!ymust[i])on(i);
	}
	int ans=d*(d-get());
	
	//find the largest gap
	for(int L=0;L<d;++L){
		if(xmust[L])continue;
		int R=L;
		while(!xmust[R+1])++R;
		//we consider the gap [L,R]
		vi last(d,-1);
		for(int r=L;r<=R;++r){
			for(int i:b[r])last[i]=r;
			for(int i=L;i<=r;++i)lasts[i].clear();
			reset();
			for(int i=0;i<d;++i){
				if(last[i]==-1){
					if(!ymust[i])on(i);
				}
				else lasts[last[i]].pb(i);
			}
			//left endpoint is r, and we try l from L to r
			for(int l=L;l<=r;++l){
				ans=min(ans,(d-(r-l+1))*(d-get()));
				for(int i:lasts[l])on(i);
			}
		}
		L=R;
	}
	pf("%d\n",ans);
}

/*
2 1 5
1 4
2 2
0 0

8

3 4 100
20 26
81 56
20 3
58 71
74 82
95 61
95 61

2840

5 7 5000
1046 365
4122 1166
4009 2896
1815 4065
4372 1651
2382 123
1475 836
3313 4005
2579 568
4300 4867
1050 3214
3589 4653

10543092
*/

Compilation message (stderr)

garden.cpp: In function 'int main()':
garden.cpp:103:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |  sf("%d%d%d",&n,&m,&d);
      |    ^
garden.cpp:106:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   int x,y;sf("%d%d",&x,&y);
      |             ^
garden.cpp:111:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   int x,y;sf("%d%d",&x,&y);
      |             ^

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