Submission #1090616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090616		namduong93	Quality Of Living (IOI10_quality)	C++14	100 / 100	1823 ms	210768 KiB

quality

/**
 *    author:  namduong93
 *    created: unknown
 *    complexity: unknown
 **/
#include <bits/stdc++.h>
using namespace std;

#define fto(i, a, b) for (int i = a; i <= b; ++i)
#define fdo(i, a, b) for (int i = a; i >= b; --i)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define SZ(x) ((int)(x).size())

int get_bit(int x, int i)
{
    return x & (1 << i);
}
int turn_bit(int x, int i) { return x | (1 << i); }
int swap_bit(int x, int i) { return x ^ (1 << i); }

typedef pair<int, int> pii;
typedef long long ll;

const int mod = 998244353;
const int N = 3001;
const int inf = 1e9 + 7;

int n;
int R, C, H, W;
int a[N][N], tmp_Q[N][N], sum[N][N];
string str;
stack<int> st;
priority_queue<pii, vector<pii>, greater<pii>> d_heap;
multiset<int> ms;

int find(int m, int Q[3001][3001]) {
    fto(i,1,R)
    fto(j,1,C) {
        if(Q[i][j] == m) tmp_Q[i][j] = 0;
        if(Q[i][j] < m) tmp_Q[i][j] = -1;
        if(Q[i][j] > m) tmp_Q[i][j] = 1;
    }
    fto(i,1,R) {
        fto(j,1,C) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + tmp_Q[i][j];
        }
    }
    bool exist = false;
    fto(i,H,R) fto(j,W,C) {
        int guess = sum[i][j] - sum[i - H][j] - sum[i][j - W] + sum[i - H][j - W];
        if(guess < 0) return -1;
        if (guess == 0) exist = true;
    }
    if(exist) return 0;
    return 1;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
    int smaller[R+1][C+1] , bigger[R+1][C+1] , arr[R+1][C+1];
    //make grid 1-indexed
    memset(smaller , 0 , sizeof(smaller)) ;
    memset(bigger , 0 , sizeof(bigger)) ;
    for(int i = 1 ; i <= R ; ++i)
    {
        for(int j = 1 ; j <= C ; ++j)
            arr[i][j] = Q[i-1][j-1] ;
    }
    //make binary search and return minimum answer
    int l = 1 , r = R*C , ans = R*C ;
    while(l <= r)
    {
        int mid = (l + r) / 2 ;
        //prepare prefix array
        for(int i = 1 ; i <= R ; ++i)
        {
            int s = 0 , b = 0 ;
            for(int j = 1 ; j <= C ; ++j)
            {
                smaller[i][j] = s + smaller[i-1][j];
                if(arr[i][j] < mid)
                    smaller[i][j]++ , ++s;
                bigger[i][j] = b + bigger[i-1][j] ;
                if(arr[i][j] > mid)
                    bigger[i][j]++ , ++b;
            }
        }
        //loop on all possible rectangles if size H*W.
        bool t = false ;
        for(int i = 1 ; i <= R-H+1 ; ++i)
        {
            for(int j = 1 ; j <= C-W+1 ; ++j)
            {
                int s = smaller[i+H-1][j+W-1] - smaller[i+H-1][j-1] - smaller[i-1][j+W-1] + smaller[i-1][j-1] ;
                int b = bigger[i+H-1][j+W-1] - bigger[i+H-1][j-1] - bigger[i-1][j+W-1] + bigger[i-1][j-1] ;
                if(s >= b)
                    t = true ;
                int n = R*C ;
                if(s == b && s <= n/2 && b <= n/2)
                    ans = min(ans , mid) ;
            }
        }
        if(t == true)
            r = mid-1 ;
        else
            l = mid+1 ;
    }
    return ans ;
}

// void Solve() {
//     cin >> R >> C >> H >> W;
//     fto(i,1,R) fto(j,1,C) {
//         cin>>a[i][j];
//     }
//     cout<<rectangle(R, C, H, W, a);
// }

// int32_t main()
// {

//     if (fopen("test.inp", "r"))
//         freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);

//     ios::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);

//     int Test = 1;
//     // cin >> Test;
//     fto(iTest, 1, Test)
//     {
//         Solve();
//     }

//     // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
//     return 0;
// }

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