Submission #204199

#	Time	Username	Problem	Language	Result	Execution time	Memory
204199		kig9981	Cultivation (JOI17_cultivation)	C++17	0 / 100	7 ms	376 KiB

cultivation

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const int SZ=1<<10;
int X, Y, tree[2*SZ], lazy[2*SZ];
vector<pair<int,int>> P;
vector<tuple<int,int,int>> Q;
vector<int> x;

void lazy_propagation(int bit, int s, int e)
{
	if(lazy[bit]>-1) {
		tree[bit]=lazy[bit];
		if(s<e) lazy[2*bit]=lazy[2*bit+1]=lazy[bit];
		lazy[bit]=-1;
	}
}

void set_tree(int n1, int n2, int v, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1) return;
	if(n1<=s && e<=n2) {
		lazy[bit]=v;
		return;
	}
	set_tree(n1,n2,v,2*bit,s,m);
	set_tree(n1,n2,v,2*bit+1,m+1,e);
	tree[bit]=min(tree[2*bit],tree[2*bit+1]);
}

int get_min(int n1, int n2, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1) return 0x7fffffff;
	if(n1<=s && e<=n2) return tree[bit];
	return min(get_min(n1,n2,2*bit,s,m),get_min(n1,n2,2*bit+1,m+1,e));
}

long long solve(int dl, int dr)
{
	int M=0;
	x.clear();
	for(auto[a,b]: P) {
		x.push_back(max(a-dl,1));
		x.push_back(min(a+dr,X)+1);
	}
	sort(x.begin(),x.end());
	x.resize(unique(x.begin(),x.end())-x.begin());
	Q.clear();
	for(auto[a,b]: P) {
		int l=lower_bound(x.begin(),x.end(),max(a-dl,1))-x.begin(), r=lower_bound(x.begin(),x.end(),min(a+dr,X)+1)-x.begin()-1;
		Q.emplace_back(b,l,r);
	}
	sort(Q.begin(),Q.end());
	Q.emplace_back(Y,0,x.size()-1);
	lazy[1]=1;
	for(auto[v,l,r]: Q) {
		M=max(M,v-get_min(l,r)-1);
		set_tree(l,r,v);
	}
	return dl+dr+M;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M;
	long long ans=0x7fffffffffffffffLL;
	cin>>X>>Y>>N;
	P.resize(N);
	for(auto &[a,b]: P) cin>>a>>b;
	sort(P.begin(),P.end());
	M=max(P[0].first-1,X-P[N-1].first);
	for(int i=1;i<N;i++) M=max(M,P[i].first-P[i-1].first-1);
	for(int i=0;i<N;i++) for(int j=i;j<N;j++) {
		int dl=P[i].first-1, dr=X-P[j].first;
		ans=min(ans,solve(dl,max(dr,M-dl)));
		ans=min(ans,solve(max(dl,M-dr),dr));
	}
	cout<<ans<<'\n';
	return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'long long int solve(int, int)':
cultivation.cpp:55:14: warning: unused variable 'b' [-Wunused-variable]
  for(auto[a,b]: P) {
              ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20