oj.uz

답안 #258658

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258658 2020-08-06T10:34:33 Z uacoder123 삶의 질 (IOI10_quality) C++14
60 / 100
 173 ms 8184 KB 
    #include <bits/stdc++.h>
    #include "quality.h"
    #include <ext/pb_ds/assoc_container.hpp>
    using namespace std;
    using namespace __gnu_pbds;
    #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;
    typedef tree<pair<lli,int>,null_type,less<pair<lli,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
    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 j=0;j<c;++j)
      {
        for(int i=0;i<r;++i)
        {
          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]) 
    {
      r=R;
      c=C;
      h=H;
      w=W;
      if(r*c>=900000)
        exit(1);
      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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 4 ms 1664 KB Output is correct
6 Correct 4 ms 1664 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 4 ms 1664 KB Output is correct
6 Correct 4 ms 1664 KB Output is correct
7 Correct 32 ms 5112 KB Output is correct
8 Correct 34 ms 4992 KB Output is correct
9 Correct 27 ms 4864 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 4 ms 1664 KB Output is correct
6 Correct 4 ms 1664 KB Output is correct
7 Correct 32 ms 5112 KB Output is correct
8 Correct 34 ms 4992 KB Output is correct
9 Correct 27 ms 4864 KB Output is correct
10 Runtime error 173 ms 8184 KB Execution failed because the return code was nonzero
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 4 ms 1664 KB Output is correct
6 Correct 4 ms 1664 KB Output is correct
7 Correct 32 ms 5112 KB Output is correct
8 Correct 34 ms 4992 KB Output is correct
9 Correct 27 ms 4864 KB Output is correct
10 Runtime error 173 ms 8184 KB Execution failed because the return code was nonzero
11 Halted 0 ms 0 KB -