제출 #288576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288576		MasterTaster	삶의 질 (IOI10_quality)	C++14	0 / 100	1 ms	512 KiB

quality

#include<bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include "quality.h"

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define endl "\n"
#define MAXN 9000000

static int R,C,H,W,Q[3001][3001],i,j,ans;
int pref[3010][3010], q[3010][3010], pom[3010][3010];
//int bit[310];
int pola;

/*pair<int, int> pos[90010];

ll sum(int x)
{
    ll ret=0;
    while (x)
    {
        ret+=bit[x];
        x-=x&(-x);
    }
    return ret;
}
void upd(int x, int val)
{
    while (x<MAXN)
    {
        bit[x]+=val;
        x+=x&(-x);
    }
    return;
}*/

bool check(int med)
{
    for (int i=0; i<R; i++)
    {
        for (int j=0; j<C; j++)
        {
            pref[i][j]=0;
            pom[i][j]=(q[i][j]<=med) ? 1 : 0;
            ///cout<<pom[i][j]<<" ";
        }
        ///cout<<endl;
    }

    ///cout<<endl;
    for (int i=0; i<R; i++)
    {
        for (int j=0; j<C; j++)
        {
            pref[i][j]=pom[i][j];
            if (i>0) pref[i][j]+=pref[i-1][j];
            if (j>0) pref[i][j]+=pref[i][j-1];
            if (i>0 && j>0) pref[i][j]-=pref[i-1][j-1];
            ///cout<<pref[i][j]<<" ";
        }
        ///cout<<endl;
    }

    for (int i=H-1; i<R; i++)
    {
        for (int j=W-1; j<C; j++)
        {
            int koliko=pref[i][j];
            if (i>=H) koliko-=pref[i-H][j];
            if (j>=W) koliko-=pref[i][j-W];
            if (i>=H && j>=W) koliko+=pref[i-H][j-W];
            if (koliko>=pola) { /*cout<<med<<" "<<i<<" "<<j<<" "<<koliko<<endl;*/ return true; }
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
    pola=H*W/2+1;
    for (int i=0; i<R; i++) for (int j=0; j<C; j++) q[i][j]=Q[i][j];

    int l=1, r=R*C;
    ll ress=-1;
    while (l<=r)
    {
        int mid=l+(r-l)/2;
        ///cout<<mid<<":"<<endl<<endl<<endl;
        if (check(mid))
        {
            ress=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return ress;
    /*int ress=R*C+1;

    int koji=H*W/2+1;
    for (int i=0; i<R; i++) for (int j=0; j<C; j++) pos[Q[i][j]]={i, j};

    for (int i=0; i<=R-H; i++)
    {
        for (int k=i; k<i+H; k++)
            for (int j=0; j<W; j++)
                { cout<<Q[k][j]<<" "; upd(Q[k][j], 1); }
        cout<<endl;
        for (int j=0; j<=C-W; j++)
        {
            int l=1, r=R*C;
            int trRess=1000000000;
            while (l<=r)
            {
                int mid=l+(r-l)/2;
                if (sum(mid)>=koji)
                {
                    trRess=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            cout<<"ee "<<trRess<<endl;
            ress=min(trRess, ress);

            for (int k=i; k<i+H; k++)
            {
                upd(Q[k][j], -1);
                if (j+W<C) upd(Q[k][j+W], 1);
            }
        }
    }

    return ress;*/
	//return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

quality.cpp:16:38: warning: 'ans' defined but not used [-Wunused-variable]
   16 | static int R,C,H,W,Q[3001][3001],i,j,ans;
      |                                      ^~~
quality.cpp:16:36: warning: 'j' defined but not used [-Wunused-variable]
   16 | static int R,C,H,W,Q[3001][3001],i,j,ans;
      |                                    ^
quality.cpp:16:34: warning: 'i' defined but not used [-Wunused-variable]
   16 | static int R,C,H,W,Q[3001][3001],i,j,ans;
      |                                  ^
quality.cpp:16:20: warning: 'Q' defined but not used [-Wunused-variable]
   16 | static int R,C,H,W,Q[3001][3001],i,j,ans;
      |                    ^
quality.cpp: In function 'bool check(int)':
quality.cpp:74:33: warning: array subscript -1 is below array bounds of 'int [3010]' [-Warray-bounds]
   74 |             int koliko=pref[i][j];
      |                        ~~~~~~~~~^

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