Submission #1073507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073507		sleepntsheep	Cultivation (JOI17_cultivation)	C++14	0 / 100	3 ms	348 KiB

cultivation

#pragma GCC optimize("O3,unroll-loops")
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>
#include <tuple>
#include <algorithm>
#include <map>
#define L(i,a,b)for(int i=a;i<b;++i)

using namespace std;

int C,Ans=1e9,R,n,x[300],y[300];

int main() {
	scanf("%d%d%d", &R, &C, &n);
  L(i,0,n)scanf("%d%d",y+i,x+i);
  auto Cal=[&](int iii){
    vector<tuple<int,int,int>>e;
    set<int>yy;
    L(k,0,n)e.emplace_back(y[k],-1,k),e.emplace_back(y[k]+iii+1,1,k),yy.insert(y[k]),yy.insert(y[k]+iii);
    sort(e.begin(),e.end());static int q[999];int hd=0,tl=0;
    multiset<int>qq,gap,pos; map<int,int>ro;
    pos.insert(0);pos.insert(C);
    gap.insert(C);
    auto Ad=[&](int x){
      if(!pos.count(x)){auto it=pos.upper_bound(x),it2=it;--it;gap.erase(gap.find(*next(it)-*it));gap.insert(x-*it);gap.insert(*it2-x);}
      pos.insert(x);
    };
    auto De=[&](int x){
      pos.erase(pos.find(x));
      if(!pos.count(x)){auto it=pos.upper_bound(x);gap.erase(gap.find(*it-x));--it;gap.erase(gap.find(x-*it));gap.insert(*next(it)-*it);};
    };
    auto Ge=[&](){return max({*gap.rbegin()-1,*pos.begin()+C-*pos.rbegin()-1});};
    int o=0;
    for(auto Y:yy){
      while(o<2*n and get<0>(e[o])<=Y){
        auto[Y,T,I]=e[o++];
        if(T<0)Ad(x[I]);else De(x[I]);
      }
      while(hd-tl>1&&q[tl+1]+R-1<=Y)qq.erase(qq.find(ro[q[tl++]]));
      qq.insert(ro[q[hd++]=Y]=Ge());
      //printf(" Ge(%d) = %d\n",Y,Ge());
      if(hd-tl>1&&q[tl]+R-1<=q[hd-1]){
        Ans=min(Ans,*qq.rbegin()+iii);
        //printf(" From %d to %d - %d\n",q[tl],q[hd-1],*qq.rbegin());
      }
    }
  };

  L(i,0,n){
    Cal(y[i]-1);Cal(R-y[i]);
    L(j,i,n){
      Cal(abs(y[i]-y[j]));
      if(abs(y[i]-y[j]))Cal(abs(y[i]-y[j])-1);
    }
  }

	printf("%d",Ans);
}

Compilation message (stderr)

cultivation.cpp: In lambda function:
cultivation.cpp:38:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         auto[Y,T,I]=e[o++];
      |             ^
cultivation.cpp: In function 'int main()':
cultivation.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%d%d", &R, &C, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:17:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   L(i,0,n)scanf("%d%d",y+i,x+i);
      |           ~~~~~^~~~~~~~~~~~~~~~

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