oj.uz

Submission #562974

# Submission time Handle Problem Language Result Execution time Memory
562974 2022-05-15T23:40:14 Z Deepesson Quality Of Living (IOI10_quality) C++17
100 / 100
 2870 ms 210724 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 35768 KB Output is correct
2 Correct 131 ms 35760 KB Output is correct
3 Correct 116 ms 35668 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 35768 KB Output is correct
2 Correct 131 ms 35760 KB Output is correct
3 Correct 116 ms 35668 KB Output is correct
4 Correct 169 ms 36200 KB Output is correct
5 Correct 167 ms 36192 KB Output is correct
6 Correct 172 ms 36140 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 35768 KB Output is correct
2 Correct 131 ms 35760 KB Output is correct
3 Correct 116 ms 35668 KB Output is correct
4 Correct 169 ms 36200 KB Output is correct
5 Correct 167 ms 36192 KB Output is correct
6 Correct 172 ms 36140 KB Output is correct
7 Correct 220 ms 38420 KB Output is correct
8 Correct 223 ms 38424 KB Output is correct
9 Correct 209 ms 38268 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 35768 KB Output is correct
2 Correct 131 ms 35760 KB Output is correct
3 Correct 116 ms 35668 KB Output is correct
4 Correct 169 ms 36200 KB Output is correct
5 Correct 167 ms 36192 KB Output is correct
6 Correct 172 ms 36140 KB Output is correct
7 Correct 220 ms 38420 KB Output is correct
8 Correct 223 ms 38424 KB Output is correct
9 Correct 209 ms 38268 KB Output is correct
10 Correct 438 ms 58172 KB Output is correct
11 Correct 445 ms 58060 KB Output is correct
12 Correct 338 ms 48832 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 35768 KB Output is correct
2 Correct 131 ms 35760 KB Output is correct
3 Correct 116 ms 35668 KB Output is correct
4 Correct 169 ms 36200 KB Output is correct
5 Correct 167 ms 36192 KB Output is correct
6 Correct 172 ms 36140 KB Output is correct
7 Correct 220 ms 38420 KB Output is correct
8 Correct 223 ms 38424 KB Output is correct
9 Correct 209 ms 38268 KB Output is correct
10 Correct 438 ms 58172 KB Output is correct
11 Correct 445 ms 58060 KB Output is correct
12 Correct 338 ms 48832 KB Output is correct
13 Correct 2870 ms 210688 KB Output is correct
14 Correct 2719 ms 210724 KB Output is correct
15 Correct 2557 ms 196268 KB Output is correct