제출 #1070342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1070342		j_vdd16	Rectangles (IOI19_rect)	C++17	0 / 100	18 ms	860 KiB

rect

#include "rect.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define ll long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

long long count_rectangles(vvi a) {
	int n = a.size();
    int m = a[0].size();

    vector<set<ii>> validRows(n);
    for (int i = 1; i < n - 1; i++) {
        vii values;
        loop(j, m) {
            values.push_back({a[i][j], j});
        }
        sort(all(values), greater<ii>{});

        map<int, int> rec;
        for (auto [val, j] : values) {
            if (rec.size() == 0) {
                rec[j] = val;
                continue;
            }

            auto next = rec.upper_bound(j);
            if (next != rec.end() && next->first - j > 1) {
                validRows[i].insert({j, next->first});
            }
            next--;
            if (j - next->first > 1) {
                validRows[i].insert({next->first, j});
            }

            rec[j] = val;
        }
    }
    vector<set<ii>> validCols(m);
    for (int j = 1; j < m - 1; j++) {
        vii values;
        loop(i, n) {
            values.push_back({a[i][j], i});
        }
        sort(all(values), greater<ii>{});

        map<int, int> rec;
        for (auto [val, i] : values) {
            if (rec.size() == 0) {
                rec[i] = val;
                continue;
            }

            auto next = rec.upper_bound(i);
            if (next != rec.end() && next->first - i > 1) {
                validCols[j].insert({i, next->first});
            }
            next--;
            if (i - next->first > 1) {
                validCols[j].insert({next->first, i});
            }

            rec[i] = val;
        }
    }

    ll result = 0;
    for (int i = 1; i < n - 1; i++) {
        for (auto [x, y] : validRows[i]) {
            int furthest = i;
            while (validRows[furthest + 1].count({x, y})) furthest++;

            vi freq(furthest - i + 1);
            for (int j = x + 1; j <= y - 1; j++) {
                for (int i2 = i; i2 <= furthest; i2++) {
                    if (validCols[j].count({i - 1, i2 + 1}))
                        freq[i2 - i]++;
                }
            }

            ll extra = 0;
            for (int k = 0; k < furthest - i + 1; k++) {
                if (freq[k] == y - x - 1)
                    extra++;
            }

            result += extra;
        }
    }

    return result;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28