oj.uz

Submission #481763

# Submission time Handle Problem Language Result Execution time Memory
481763 2021-10-21T17:24:50 Z SlavicG Quality Of Living (IOI10_quality) C++17
100 / 100
 2705 ms 106112 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; //didnt qualify to iom because of this line :(
        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;
      |                   ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 70848 KB Output is correct
2 Correct 98 ms 70896 KB Output is correct
3 Correct 90 ms 70836 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 70848 KB Output is correct
2 Correct 98 ms 70896 KB Output is correct
3 Correct 90 ms 70836 KB Output is correct
4 Correct 121 ms 71208 KB Output is correct
5 Correct 124 ms 71204 KB Output is correct
6 Correct 123 ms 71108 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 70848 KB Output is correct
2 Correct 98 ms 70896 KB Output is correct
3 Correct 90 ms 70836 KB Output is correct
4 Correct 121 ms 71208 KB Output is correct
5 Correct 124 ms 71204 KB Output is correct
6 Correct 123 ms 71108 KB Output is correct
7 Correct 160 ms 72324 KB Output is correct
8 Correct 164 ms 72388 KB Output is correct
9 Correct 164 ms 72296 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 70848 KB Output is correct
2 Correct 98 ms 70896 KB Output is correct
3 Correct 90 ms 70836 KB Output is correct
4 Correct 121 ms 71208 KB Output is correct
5 Correct 124 ms 71204 KB Output is correct
6 Correct 123 ms 71108 KB Output is correct
7 Correct 160 ms 72324 KB Output is correct
8 Correct 164 ms 72388 KB Output is correct
9 Correct 164 ms 72296 KB Output is correct
10 Correct 455 ms 78692 KB Output is correct
11 Correct 411 ms 78688 KB Output is correct
12 Correct 294 ms 76728 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 70848 KB Output is correct
2 Correct 98 ms 70896 KB Output is correct
3 Correct 90 ms 70836 KB Output is correct
4 Correct 121 ms 71208 KB Output is correct
5 Correct 124 ms 71204 KB Output is correct
6 Correct 123 ms 71108 KB Output is correct
7 Correct 160 ms 72324 KB Output is correct
8 Correct 164 ms 72388 KB Output is correct
9 Correct 164 ms 72296 KB Output is correct
10 Correct 455 ms 78692 KB Output is correct
11 Correct 411 ms 78688 KB Output is correct
12 Correct 294 ms 76728 KB Output is correct
13 Correct 2705 ms 106008 KB Output is correct
14 Correct 2649 ms 106112 KB Output is correct
15 Correct 2501 ms 105996 KB Output is correct