Submission #1181873

#TimeUsernameProblemLanguageResultExecution timeMemory
1181873sleepntsheepCultivation (JOI17_cultivation)C++20
Compilation error
0 ms0 KiB
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>

int r,c,n,ans=2e9+2;
struct pt{int x,y;}p[333];
struct DQ{
    int y[999999],x[999999],hd,tl;
    void cl(){ hd=0;tl=1; }
    DQ(){cl();}
    void ins(int t,int va){
	while(hd>=tl&&x[hd]<=va)--hd;
	++hd;
	x[hd]=va;
	y[hd]=t;
    }
    void tim(int t){ while(hd>=tl&&y[tl]<t)++tl; }
    int max(int t){ tim(t); return x[tl]; }
}L,R,LR;

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);
    std::sort(p,p+n,[](pt&a,pt&b){return a.x-b.x?a.x<b.x:a.y<b.y;});
    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=[&](int dw){
	L.cl();R.cl();LR.cl();

	int ban=0;
	auto Chk=[&](int i){
	    if(i<1)i=1;
	    std::vector<int>e;
	    for(int j=0;j<n;++j)if((p[j].x<=i&&p[j].x+dw>=i))
		e.push_back(p[j].y);
	    if(e.empty()){
		ban=i;
		return;
	    }
	    int gapmax=0;
	    for(int i=1;i<(int)e.size();++i)
		gapmax=std::max(gapmax,e[i]-e[i-1]-1);

	    L.ins(i,e[0]-1);
	    R.ins(i,c-e.back());
	    LR.ins(i,gapmax);

	    if(ban<=i-r){
		ans=std::min(ans,dw+0ll+std::max(L.max(i-r+1)+R.max(i-r+1),LR.max(i-r+1)));
	    }
	};

	std::vector<int>qwq;
	for(int i=0;i<n;++i){
	    qwq.push_back(p[i].x-1); qwq.push_back(p[i].x);
	    qwq.push_back(p[i].x+dw+1);
	    qwq.push_back(p[i].x+dw);
	}
	std::sort(qwq.begin(),qwq.end());
	qwq.resize(std::distance(qwq.begin(),std::unique(qwq.begin(),qwq.end())));
	for(auto dw:qwq)Chk(dw);
    };

    std::sort(p,p+n,[](pt&a,pt&b){return a.x-b.x?a.x<b.x:a.y<b.y;});
    std::vector<int>ud_cands={0},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)
	    if(p[j].x>p[i].x)
		ud_cands.push_back(p[j].x-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;});
    for(auto ud:ud_cands)CC(ud);

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

Compilation message (stderr)

cultivation.cpp: In lambda function:
cultivation.cpp:51:29: error: no matching function for call to 'min(int&, long long int)'
   51 |                 ans=std::min(ans,dw+0ll+std::max(L.max(i-r+1)+R.max(i-r+1),LR.max(i-r+1)));
      |                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:61,
                 from cultivation.cpp:2:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
cultivation.cpp:51:29: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   51 |                 ans=std::min(ans,dw+0ll+std::max(L.max(i-r+1)+R.max(i-r+1),LR.max(i-r+1)));
      |                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:61,
                 from cultivation.cpp:2:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
cultivation.cpp:51:29: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   51 |                 ans=std::min(ans,dw+0ll+std::max(L.max(i-r+1)+R.max(i-r+1),LR.max(i-r+1)));
      |                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from cultivation.cpp:2:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3449 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note:   template argument deduction/substitution failed:
cultivation.cpp:51:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   51 |                 ans=std::min(ans,dw+0ll+std::max(L.max(i-r+1)+R.max(i-r+1),LR.max(i-r+1)));
      |                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from cultivation.cpp:2:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3455 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note:   template argument deduction/substitution failed:
cultivation.cpp:51:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   51 |                 ans=std::min(ans,dw+0ll+std::max(L.max(i-r+1)+R.max(i-r+1),LR.max(i-r+1)));
      |                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d%d%d",&r,&c,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
cultivation.cpp:24:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     for(int i=0;i<n;++i)scanf("%d%d",&p[i].x,&p[i].y);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~