Submission #1182036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182036		sleepntsheep	Cultivation (JOI17_cultivation)	C++20	80 / 100	2096 ms	3772 KiB

cultivation

#pragma GCC optimize("O2,unroll-loops")
#include<assert.h>
#include<stdio.h>
#include<set>
#include<algorithm>
#include<vector>

int r,c,n;long long ans=1e10;
std::vector<int>xx,yy;
struct pt{int x,y,cx,cy;}p[333];

struct DQ{
    long long y[5555555],x[5555555];int hd,tl;
    void cl(){ hd=0;tl=1; }
    DQ(){cl();}
    void ins(long long t,long long va){
	while(hd>=tl&&x[hd]<=va)--hd;
	++hd;
	x[hd]=va;
	y[hd]=t;
    }
    void tim(long long t){ while(hd>=tl&&y[tl]<t)++tl; }
    long long max(long long t){ tim(t); return x[tl]; }
}L,R,LR;

template <typename T>
void sortunique(std::vector<T>&v){
    std::sort(v.begin(),v.end());
    v.resize(std::distance(v.begin(),std::unique(v.begin(),v.end())));
}

struct GAPMAINTAINER{
    std::multiset<int>s,gc;
    int l,r,g;
    void ins(int y){
	if(s.find(y)==s.end()){
	    auto it=s.upper_bound(y);
	    if(it!=s.end()&&(it)!=s.begin()){
		gc.erase(gc.find(*it-*prev(it)));
	    }
	    if(it!=s.end()) gc.insert(*it-y);
	    if((it)!=s.begin())gc.insert(y-*prev(it));
	    s.insert(y);
	    if(gc.size())
		g=*gc.rbegin()-1;
	    if(s.size()){
		l=*s.begin()-1;
		r=c-*s.rbegin();
	    }
	}else
	s.insert(y);
    }
    void rem(int y){
	if(s.find(y)!=s.end()){
	    auto it=s.upper_bound(y),iy=s.lower_bound(y);
	    if(it!=s.end())gc.erase(gc.find(*it-y));
	    if(iy!=s.begin())gc.erase(gc.find(y-*prev(iy)));
	    if(it!=s.end()&&iy!=s.begin())gc.insert(*it-*prev(iy));
	    s.erase(s.find(y));
	    if(gc.size())
		g=*gc.rbegin()-1;
	    if(s.size()){
		l=*s.begin()-1;
		r=c-*s.rbegin();
	    }
	}
	else
	s.erase(s.find(y));
    }
};

int pgap[333][333],plef[333][333],prig[333][333];

void precompute(){
    std::vector<int>tag[333];
    for(int i=0;i<n;++i) tag[p[i].cx].push_back(i);
    for(int i=0;i<(int)xx.size();++i){
	GAPMAINTAINER gm;
	for(int j=i;j<(int)xx.size();++j){
	    for(auto id:tag[j])gm.ins(p[id].y);
	    pgap[i][j]=gm.g;
	    plef[i][j]=gm.l;
	    prig[i][j]=gm.r;
	}
    }
}

int main(){
    scanf("%d%d%d",&r,&c,&n);
    for(int i=0;i<n;++i)scanf("%d%d",&p[i].x,&p[i].y),xx.push_back(p[i].x),yy.push_back(p[i].y);
    sortunique(xx),sortunique(yy);
    for(int i=0;i<n;++i)p[i].cx=std::lower_bound(xx.begin(),xx.end(),p[i].x)-xx.begin(),p[i].cy=std::lower_bound(yy.begin(),yy.end(),p[i].y)-yy.begin();
    precompute();

    std::sort(p,p+n,[](pt&a,pt&b){return a.y-b.y?a.y<b.y:a.x<b.x;});
    n=std::unique(p,p+n,[](pt&a,pt&b){return a.x==b.x&&a.y==b.y;})-p;

    auto CC_=[&](long long dw){
	L.cl();R.cl();LR.cl();

	enum{ ADD,DEL,CHK};
	struct Event{ long long type,x,cx; };

	std::vector<Event>e1;
	int i1{},i2{},i3{},i4{};

	while(i1<n||i2<n||i3<n||i4<n){
	    auto chk=[&](long long x){
		if(i1<n&&p[i1].x<x)return 0;
		if(i2<n&&p[i2].x+dw+1<x)return 0;
		if(i3<n&&p[i3].x+dw<x)return 0;
		if(i4<n&&p[i4].x-1<x)return 0;
		return 1;
	    };
	    if(i1<n&&chk(p[i1].x)){
		e1.push_back((Event){ADD,p[i1].x,p[i1].cx});++i1;
		continue;
	    }
	    else if(i2<n&&chk(p[i2].x+dw+1)){
		e1.push_back((Event){DEL,p[i2++].x+dw+1,-1});
		continue;
	    }
	    else{
		if(i3<n&&chk(p[i3].x+dw)){
		    e1.push_back((Event){CHK,p[i3++].x+dw,-1});
		    continue;
		}
		if(i4<n&&chk(p[i4].x-1)){
		    e1.push_back((Event){CHK,p[i4++].x-1,-1});
		}
	    }
	}

	static int qu[999],hd,tl,l1,r1;
	hd=0;tl=1;

	long long x;

	for(auto&ee:e1){
	    x=ee.x;
	    if(ee.type==ADD){
		qu[++hd]=ee.cx;
	    }else if(ee.type==DEL){
		++tl;
	    }
	    if(hd<tl)L.ins(x,1e9),R.ins(x,1e9);
	    if(ee.type==CHK){
		if(hd>=tl){
		    l1=qu[tl],r1=qu[hd];
		    L.ins(x,plef[l1][r1]);
		    R.ins(x,prig[l1][r1]);
		    LR.ins(x,pgap[l1][r1]);
		}
		ans=std::min(ans,dw+0ll+std::max(L.max(x-r+1)+R.max(x-r+1),LR.max(x-r+1)));
	    }
	}
    };

    std::vector<long long>ud_cands={0};

    {
	std::sort(p,p+n,[](pt&a,pt&b){return a.x-b.x?a.x<b.x:a.y<b.y;});

	std::vector<long long>uu={p[0].x-1},dd={r-p[n-1].x};

	for(int i=0;i<n;++i){
	    uu.push_back(p[i].x-1);
	    dd.push_back(r-p[i].x);
	    for(int j=i;j<n;++j){
		ud_cands.push_back(p[j].x-0ll-p[i].x-1);
		ud_cands.push_back(r-p[j].x-0ll+p[i].x-1); ud_cands.push_back(r+p[j].x-0ll-p[i].x+1);
	    }
	}

	for(auto u:uu)for(auto d:dd)ud_cands.push_back(u+d);
    }

    std::sort(ud_cands.begin(),ud_cands.end());
    ud_cands.resize(std::distance(ud_cands.begin(),std::unique(ud_cands.begin(),ud_cands.end())));

    std::sort(p,p+n,[](pt&a,pt&b){return a.y-b.y?a.y<b.y:a.x<b.x;});
    std::sort(p,p+n,[](pt&a,pt&b){return a.x-b.x?a.x<b.x:a.y<b.y;});
    for(auto ud:ud_cands){
	CC_(ud);
    }

    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d%d%d",&r,&c,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
cultivation.cpp:90:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     for(int i=0;i<n;++i)scanf("%d%d",&p[i].x,&p[i].y),xx.push_back(p[i].x),yy.push_back(p[i].y);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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