Submission #810590

#	Time	Username	Problem	Language	Result	Execution time	Memory
810590		NemanjaSo2005	Garden (JOI23_garden)	C++17	75 / 100	2031 ms	23500 KiB

garden

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,M,D,K;
int nizx[500005],nizy[500005];
struct tipb{
   int x,y,poz;
} niz[500005];
bool pox(tipb a,tipb b){
   return a.x<b.x;
}
bool poy(tipb a,tipb b){
   return a.y<b.y;
}
struct slog{
   int ly,ry,mr;
} st[1050000];
int ayniz[500005];
slog opr(slog a,slog b){
   if(a.mr==-1)
      return b;
   if(b.mr==-1)
      return a;
   slog ret;
   ret.ly=a.ly;
   ret.ry=b.ry;
   ret.mr=max(a.mr,b.mr);
   ret.mr=max(ret.mr,b.ly-a.ry);
   return ret;
}
void toggle(int gde,bool uklj){
   int g2=gde+K-1;
   if(!uklj)
      st[g2].mr=-1;
   else{
      st[g2].ly=st[g2].ry=ayniz[gde];
      st[g2].mr=0;
   }
   g2>>=1;
   while(g2){
      st[g2]=opr(st[g2<<1],st[(g2<<1)+1]);
      g2>>=1;
   }
   return;
}
vector<int> bucket[5005];
int getmr(){
   return max(st[1].mr-1,D-(st[1].ry-st[1].ly+1));
}
bool aktb[5005];
void ceobuck(int idx,bool sta){
   if(aktb[idx]==sta)
      return;
   aktb[idx]=sta;
   for(int i=0;i<bucket[idx].size();i++)
      toggle(bucket[idx][i],sta);
   return;
}
clock_t poc;
int main(){
   poc=clock();
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cin>>N>>M>>D;
   K=1;
   while(K<N+M)
      K*=2;
   for(int i=1;i<=2*K;i++)
      st[i].mr=-1;
   for(int i=1;i<=N;i++)
      cin>>nizx[i]>>nizy[i];
   sort(nizx+1,nizx+1+N);
   sort(nizy+1,nizy+1+N);
   for(int i=1;i<=M;i++)
      cin>>niz[i].x>>niz[i].y;
   sort(niz+1,niz+1+M,poy);
   int p1=1,p2=1;
   while(p1<=N or p2<=M){
      int koji;
      if(p1>N)
         koji=2;
      else if(p2>M)
         koji=1;
      else if(nizy[p1]<niz[p2].y)
         koji=1;
      else
         koji=2;
      if(koji==1){
         ayniz[p1+p2-1]=nizy[p1];
         toggle(p1+p2-1,true);
         p1++;
      }
      else{
         ayniz[p1+p2-1]=niz[p2].y;
         niz[p2].poz=p1+p2-1;
         p2++;
      }
   }
   for(int i=1;i<=M;i++)
      bucket[niz[i].x].push_back(niz[i].poz);
   for(int i=0;i<D;i++)
      ceobuck(i,false);
   int res=D*(D-getmr());
   double maxtime=1.3*CLOCKS_PER_SEC;
  // for(int i=1;i<=2*K;i++){
   //   cout<<i<<": "<<st[i].ly<<" "<<st[i].ry<<" "<<st[i].mr<<endl;
  // }
   for(int p=1;p<N;p++){
      if(clock()-poc>=maxtime)
         break;
      if(nizx[p]==nizx[p+1] or nizx[p]+1==nizx[p+1])
         continue;
      for(int i=0;i<=nizx[p];i++)
         ceobuck(i,false);
      for(int i=nizx[p+1];i<D;i++)
         ceobuck(i,false);
      for(int i=nizx[p]+1;i<nizx[p+1];i++)
         ceobuck(i,true);


      for(int i=nizx[p];i<nizx[p+1];i++){
         if(clock()-poc>=maxtime)
            break;
         ceobuck(i,false);
         for(int j=nizx[p+1];j>i+1;j--){
           // if(clock()-poc>=maxtime)
             //  break;
            ceobuck(j,false);
            //cout<<i<<" "<<j<<" "<<(D-(j-i-1))*(D-getmr())<<endl;
            res=min(res,(D-(j-i-1))*(D-getmr()));
         }
         for(int j=nizx[p+1];j>i+1;j--)
            ceobuck(j,true);
      }
   }
   maxtime=1.9*CLOCKS_PER_SEC;
   for(int i=0;i<nizx[1];i++)
      ceobuck(i,true);
   for(int j=nizx[N]+1;j<D;j++)
      ceobuck(j,true);
   for(int i=nizx[1];i<=nizx[N];i++)
      ceobuck(i,false);
   for(int i=nizx[N];i+1<nizx[1]+D;i++){
      if(clock()-poc>maxtime)
         break;
      ceobuck(i%D,false);
      for(int j=nizx[1]+D;j>i+1;j--){
         ceobuck(j%D,false);
         res=min(res,(D-(j-i-1))*(D-getmr()));
      }
      for(int j=nizx[1]+D;j>i+1;j--)
         ceobuck(j%D,true);
   }
   maxtime=1.99*CLOCKS_PER_SEC;
   for(int i=0;i<D;i++)
      ceobuck(i,false);


   for(int i=nizx[1]+D-2;i>=nizx[N];i--){
      if(clock()-poc>maxtime)
         break;
      ceobuck((i+1)%D,true);
      for(int j=nizx[1]+D;j>i+1;j--){
         ceobuck(j%D,false);
         res=min(res,(D-(j-i-1))*(D-getmr()));
      }
      for(int j=nizx[1]+D;j>i+1;j--)
         ceobuck(j%D,true);
   }

   cout<<res<<"\n";
   return 0;
}

Compilation message (stderr)

garden.cpp: In function 'void ceobuck(int, bool)':
garden.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for(int i=0;i<bucket[idx].size();i++)
      |                ~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 0 / 25