Submission #1009919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009919		u_suck_o	Quality Of Living (IOI10_quality)	C++17	60 / 100	5012 ms	29520 KiB

quality

#include "bits/stdc++.h"
#include "quality.h"

using namespace std;

multiset<int> s;
auto it = s.begin();
int ans = INT_MAX;

int add(int e) {
    s.insert(e);
    if (e >= *it) return 1;
    else return -1;
}

int subtract(int e) {
    if (e == *it) {
        if (s.find(e) == it) {
            it++;
            s.erase(prev(it));
            return -1;
        } else {
            s.erase(s.find(e));
            return 1;
        }
    } else {
        s.erase(s.find(e));
        if (e > *it) return -1;
        else return 1;
    }
}

void upd(int cnt) {
    if (cnt > 0)
        for (int k = 0; k < cnt/2; k++) it++;
    else
        for (int k = 0; k < (-cnt)/2; k++) it--;
    ans = min(ans, *it);
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            s.insert(Q[i][j]);
        }
    }
    it = s.begin();
    upd(H*W);
    
    for (int i = 0; i+H-1 < R; i++) {
        if (i % 2 == 0) {
            //from above
            if (i != 0) {
                int cnt = 0;
                for (int k = 0; k < W; k++) {
                    cnt += add(Q[i+H-1][k]);
                    cnt += subtract(Q[i-1][k]);
                }
                upd(cnt);
            }
            
            //go right
            for (int j = 1; j+W-1 < C; j++) {
                int cnt = 0;
                for (int k = i; k < i+H; k++) {
                    cnt += add(Q[k][j+W-1]);
                    cnt += subtract(Q[k][j-1]);
                }
                upd(cnt);
            }
        } else {
            //from above
            int cnt = 0;
            for (int k = C-W; k < C; k++) {
                cnt += add(Q[i+H-1][k]);
                cnt += subtract(Q[i-1][k]);
            }
            upd(cnt);
            
            //go left
            for (int j = C-W-1; j >= 0; j--) {
                int cnt = 0;
                for (int k = i; k < i+H; k++) {
                    cnt += add(Q[k][j]);
                    cnt += subtract(Q[k][j+W]);
                }
                upd(cnt);
            }
        }
    }
    return ans;
}

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