oj.uz

Submission #1073506

# Submission time Handle Problem Language Result Execution time Memory
1073506 2024-08-24T15:30:29 Z sleepntsheep Cultivation (JOI17_cultivation) C++17
0 / 100
 3 ms 348 KB 
#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]));
  }

	printf("%d",Ans);
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -