Submission #562974

#	Time	Username	Problem	Language	Result	Execution time	Memory
562974		Deepesson	Quality Of Living (IOI10_quality)	C++17	100 / 100	2870 ms	210724 KiB

quality

#include <bits/stdc++.h>
#include "quality.h"
#define MAX 11000000

typedef std::pair<int,int> pii;
#define MINM 3005
pii vals[MAX];
int matriz[MINM][MINM]={};
int getval(int x,int y){
    if(x<0||y<0)return 0;
    return matriz[x][y];
}

int getrectangle(int x1,int y1,int x2,int y2){
    return getval(x2,y2) + getval(x1-1,y1-1) - getval(x2,y1-1) - getval(x1-1,y2);
}

bool tentar(int p,int N,int M,int H,int W){
    memset(matriz,0,sizeof(matriz));

   // std::cout<<"Processando "<<p<<"\n";
    for(int i=0;i!=p;++i){
        auto z = vals[i];
       // std::cout<<"Add "<<z.first<<" "<<z.second<<"\n";
        matriz[z.first][z.second]++;
    }
    for(int i=0;i!=MINM-3;++i){
        int s=0;
        for(int j=0;j!=MINM-3;++j){
            s+=matriz[i][j];
            matriz[i][j]=s;
            if(i)
            matriz[i][j]+=matriz[i-1][j];
        }
    }

    int precisa = (H*W)/2;

  /*  for(int i=0;i!=N;++i){
        for(int j=0;j!=M;++j)
            std::cout<<matriz[i][j]<<" ";
        std::cout<<"\n";
    }
    std::cout<<"\n";*/
    for(int i=0;i!=N;++i){
        for(int j=0;j!=M;++j){
            int x2=i+H-1,y2=j+W-1;
            if(x2>=N||y2>=M)continue;
            int x = getrectangle(i,j,x2,y2);
            if(x>precisa)return true;
        }
    }
    return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    for(int i=0;i!=R;++i){
        for(int j=0;j!=C;++j){
            vals[Q[i][j]-1]={i,j};
        }
    }
    int la=0,ra=R*C;
    while(la<ra){
        int m = (la+ra)/2;

        if(tentar(m,R,C,H,W)){
            ra=m;
        }else la=m+1;
    }
    return la;
}

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