Submission #481762

# Submission time Handle Problem Language Result Execution time Memory
481762 2021-10-21T17:19:31 Z SlavicG Quality Of Living (IOI10_quality) C++17
100 / 100
2719 ms 146948 KB
#include"quality.h"
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
const int N = 3001;
int p1[N][N];
int p2[N][N];

int smaller(int x1, int y1, int x2, int y2){
    return p1[x2][y2] - p1[x1 - 1][y2] - p1[x2][y1 - 1] + p1[x1 - 1][y1 - 1];
}
 
int fuck(int x1, int y1, int x2, int y2){
    return p2[x2][y2] - p2[x1 - 1][y2] - p2[x2][y1 - 1] + p2[x1 - 1][y1 - 1];
}

int rectangle(int n, int m, int a, int b, int c[3001][3001]){
    int ans = INT_MAX;
 
    int l = 1,r = n * m;
    while(l <= r)
    {
        int mid = l + r >> 1;
        forn(i, N)forn(j, N)p1[i][j] = p2[i][j] = 0;
        for(int i = 0;i < n;++i){
            for(int j = 0;j < m;++j){
                if(c[i][j] < mid)p1[i + 1][j + 1] = 1;
                if(c[i][j] > mid)p2[i + 1][j + 1] = 1;
            }
        }
 
        for(int i = 1;i <= n;++i){
            for(int j = 1;j <= m;++j){
                p1[i][j] += p1[i - 1][j] + p1[i][j - 1] - p1[i - 1][j - 1];
                p2[i][j] += p2[i - 1][j] + p2[i][j - 1] - p2[i - 1][j - 1];
            }
        }
 
        bool ok = false;
        for(int i = 0;i + a - 1 < n;++i){
            for(int j = 0;j + b - 1 < m;++j){
                int sm = smaller(i + 1, j + 1, i + a, j + b);
                int gr = fuck(i + 1, j + 1, i + a, j + b);
 
                if(sm == gr){
                    ans = min(ans, mid);
                    ok = true;
                }else if(sm > gr)ok = true;
            }
        }
 
        if(ok){
            r = mid - 1;
        }else l = mid + 1;
    }
    return ans;
}   

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:32:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int mid = l + r >> 1;
      |                   ~~^~~
# Verdict Execution time Memory Grader output
1 Correct 84 ms 70904 KB Output is correct
2 Correct 89 ms 70912 KB Output is correct
3 Correct 92 ms 70896 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 84 ms 70904 KB Output is correct
2 Correct 89 ms 70912 KB Output is correct
3 Correct 92 ms 70896 KB Output is correct
4 Correct 131 ms 71164 KB Output is correct
5 Correct 114 ms 71204 KB Output is correct
6 Correct 120 ms 71108 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 84 ms 70904 KB Output is correct
2 Correct 89 ms 70912 KB Output is correct
3 Correct 92 ms 70896 KB Output is correct
4 Correct 131 ms 71164 KB Output is correct
5 Correct 114 ms 71204 KB Output is correct
6 Correct 120 ms 71108 KB Output is correct
7 Correct 161 ms 72324 KB Output is correct
8 Correct 160 ms 72844 KB Output is correct
9 Correct 149 ms 72752 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 84 ms 70904 KB Output is correct
2 Correct 89 ms 70912 KB Output is correct
3 Correct 92 ms 70896 KB Output is correct
4 Correct 131 ms 71164 KB Output is correct
5 Correct 114 ms 71204 KB Output is correct
6 Correct 120 ms 71108 KB Output is correct
7 Correct 161 ms 72324 KB Output is correct
8 Correct 160 ms 72844 KB Output is correct
9 Correct 149 ms 72752 KB Output is correct
10 Correct 430 ms 85420 KB Output is correct
11 Correct 414 ms 85316 KB Output is correct
12 Correct 288 ms 80040 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 84 ms 70904 KB Output is correct
2 Correct 89 ms 70912 KB Output is correct
3 Correct 92 ms 70896 KB Output is correct
4 Correct 131 ms 71164 KB Output is correct
5 Correct 114 ms 71204 KB Output is correct
6 Correct 120 ms 71108 KB Output is correct
7 Correct 161 ms 72324 KB Output is correct
8 Correct 160 ms 72844 KB Output is correct
9 Correct 149 ms 72752 KB Output is correct
10 Correct 430 ms 85420 KB Output is correct
11 Correct 414 ms 85316 KB Output is correct
12 Correct 288 ms 80040 KB Output is correct
13 Correct 2719 ms 146948 KB Output is correct
14 Correct 2678 ms 146944 KB Output is correct
15 Correct 2490 ms 142700 KB Output is correct