oj.uz

Submission #775759

# Submission time Handle Problem Language Result Execution time Memory
775759 2023-07-06T21:44:46 Z DobromirAngelov Quality Of Living (IOI10_quality) C++14
100 / 100
 2348 ms 141492 KB 
#include<bits/stdc++.h>
#include "quality.h"

using namespace std;

const int MAXN=3005;
const int INF=1e9+5;

int n,m;
int h,w;
int half;
int pref[MAXN][MAXN];
int minPoss1[MAXN][MAXN];
int minPoss2[MAXN][MAXN];

bool check(int x,int q[][3001])
{
    pref[0][0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(i>0 && j>0) pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
            else if(i>0) pref[i][j]=pref[i-1][j];
            else if(j>0) pref[i][j]=pref[i][j-1];
            if(q[i][j]<x) pref[i][j]++;

            if(i>=h-1 && j>=w-1)
            {
                int a1=0,a2=0,b=0;
                if(i>=h) a1=pref[i-h][j];
                if(j>=w) a2=pref[i][j-w];
                if(i>=h && j>=w) b=pref[i-h][j-w];
                if(pref[i][j]-a1-a2+b>=half) return 1;
            }
        }
    }

    return 0;
}

int find_ans(int x,int q[][3001])
{
    deque<int> dq;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            while(!dq.empty() && dq.front()<=j-w) dq.pop_front();
            if(q[i][j]>=x)
            {
                while(!dq.empty() && q[i][j]<q[i][dq.back()]) dq.pop_back();
                dq.push_back(j);
            }
            if(!dq.empty()) minPoss1[i][j]=q[i][dq.front()];
            else minPoss1[i][j]=INF;
        }
        while(!dq.empty()) dq.pop_back();
    }

    for(int j=0;j<m;j++)
    {
        for(int i=0;i<n;i++)
        {
            while(!dq.empty() && dq.front()<=i-h) dq.pop_front();
            if(minPoss1[i][j]>=x)
            {
                while(!dq.empty() && minPoss1[i][j]<minPoss1[dq.back()][j]) dq.pop_back();
                dq.push_back(i);
            }
            if(!dq.empty()) minPoss2[i][j]=minPoss1[dq.front()][j];
            else minPoss2[i][j]=INF;
        }
        while(!dq.empty()) dq.pop_back();
    }

    int ans=INF;
    pref[0][0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(i>0 && j>0) pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
            else if(i>0) pref[i][j]=pref[i-1][j];
            else if(j>0) pref[i][j]=pref[i][j-1];
            if(q[i][j]<x) pref[i][j]++;

            if(i>=h-1 && j>=w-1)
            {
                int a1=0,a2=0,b=0;
                if(i>=h) a1=pref[i-h][j];
                if(j>=w) a2=pref[i][j-w];
                if(i>=h && j>=w) b=pref[i-h][j-w];
                if(pref[i][j]-a1-a2+b>=half) ans=min(ans, minPoss2[i][j]);
            }
        }
    }

    return ans;
}

int rectangle(int R,int C,int H,int W,int q[3001][3001])
{
    n=R, m=C;
    h=H, w=W;
    half=h*w/2;
    int l=1,r=n*m;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid,q)) r=mid;
        else l=mid+1;
    }

    return find_ans(l,q);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 692 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 692 KB Output is correct
4 Correct 3 ms 2112 KB Output is correct
5 Correct 3 ms 2104 KB Output is correct
6 Correct 3 ms 2108 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 692 KB Output is correct
4 Correct 3 ms 2112 KB Output is correct
5 Correct 3 ms 2104 KB Output is correct
6 Correct 3 ms 2108 KB Output is correct
7 Correct 18 ms 7024 KB Output is correct
8 Correct 19 ms 7020 KB Output is correct
9 Correct 16 ms 6744 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 692 KB Output is correct
4 Correct 3 ms 2112 KB Output is correct
5 Correct 3 ms 2104 KB Output is correct
6 Correct 3 ms 2108 KB Output is correct
7 Correct 18 ms 7024 KB Output is correct
8 Correct 19 ms 7020 KB Output is correct
9 Correct 16 ms 6744 KB Output is correct
10 Correct 212 ms 32780 KB Output is correct
11 Correct 220 ms 32892 KB Output is correct
12 Correct 107 ms 24996 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 692 KB Output is correct
4 Correct 3 ms 2112 KB Output is correct
5 Correct 3 ms 2104 KB Output is correct
6 Correct 3 ms 2108 KB Output is correct
7 Correct 18 ms 7024 KB Output is correct
8 Correct 19 ms 7020 KB Output is correct
9 Correct 16 ms 6744 KB Output is correct
10 Correct 212 ms 32780 KB Output is correct
11 Correct 220 ms 32892 KB Output is correct
12 Correct 107 ms 24996 KB Output is correct
13 Correct 2348 ms 141376 KB Output is correct
14 Correct 2221 ms 141492 KB Output is correct
15 Correct 1996 ms 141384 KB Output is correct