Submission #258685

#	Time	Username	Problem	Language	Result	Execution time	Memory
258685		uacoder123	Quality Of Living (IOI10_quality)	C++14	100 / 100	3388 ms	175480 KiB

quality

    #include <bits/stdc++.h>
    using namespace std;
    #define F first
    #define S second
    #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
    #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
    #define all(x) (x).begin(), (x).end()
    #define sz(x) int(x.size())
    #define mp(i,a) make_pair(i,a)
    #define pb(a) push_back(a)
    #define bit(x,b) (x&(1LL<<b))
     
    typedef int lli;
    typedef pair <lli,lli> ii;
    typedef pair <lli,ii> iii;
    typedef vector <lli> vi;
    int r,c,h,w,arr[3001][3001],pr[3001],p[3001][3001];
    int check(int m)
    {
      int s=0,ch=0;
      for(int i=0;i<r;++i)
      {
        p[i+1][c-w+1]=0;
        for(int j=c-w;j<c;++j)
        {
          if(arr[i][j]<m)
            p[i+1][c-w+1]+=-1;
          else if(arr[i][j]>m)
            p[i+1][c-w+1]+=1;
        }
        if(i>=h)
          s-=p[i-h+1][c-w+1];
        s+=p[i+1][c-w+1];
        if(i>=h-1)
        {
          pr[i]=s;
          if(s<=0)
            ch=1;
        }
      }
      if(ch)
        return(ch);
      for(int i=0;i<r;++i)
      {
      for(int j=0;j<c;++j)
      {
          p[i+1][j+1]=p[i][j+1];
          if(arr[i][j]<m)
            p[i+1][j+1]+=-1;
          else if(arr[i][j]>m)
            p[i+1][j+1]+=1;
      }
    }
      for(int i=h-1;i<r;++i)
      {
        for(int j=c-w-1;j>=0;--j)
        {
          pr[i]=pr[i]-(p[i+1][j+w+1]-p[i-h+1][j+w+1])+p[i+1][j+1]-p[i+1-h][j+1];
          if(pr[i]<=0)
            return ch=1;
        }
      }
      return(ch);
    }
    int rectangle(int R, int C, int H, int W, int Q[3001][3001]) 
    {
     
          ios_base::sync_with_stdio(false);
          cin.tie(NULL);
      r=R;
      c=C;
      h=H;
      w=W;
      for(int i=0;i<r;++i)
        for(int j=0;j<c;++j)
          arr[i][j]=Q[i][j];
      int le=1,ri=r*c,ans=r*c;
      while(le<=ri)
      {
        int mi=(le+ri)/2;
        if(check(mi))
        {
          ri=mi-1;
          ans=mi;
        }
        else
        {
          le=mi+1;
        }
      }
      return(ans);
    }

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20