Submission #247479

#	Time	Username	Problem	Language	Result	Execution time	Memory
247479		tictaccat	Rectangles (IOI19_rect)	C++14	0 / 100	10 ms	1280 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

bool inside(vector<int> &v, int e) {
    return find(v.begin(), v.end(), e) != v.end();
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	vector<vector<int>> row(n*m), col(n*m);
    //row edges
    for (int i = 0; i < n; i++) {
        vector<pair<int,int>> b(m);
        for (int j = 0; j < m; j++) b[j] = make_pair(a[i][j], j);
        sort(b.begin(), b.end());
        set<int> s;
        for (int k = b.size()-1; k >= 0; k--) {
            int j = b[k].second;
            auto it = s.lower_bound(j);
            if (it != s.end()) {
                if (abs(*it - j) > 1) row[i*m + j + 1].push_back(*it - 1); 
                //if (i == 1 && j == 1) cout << "!! " << *it << "\n";
                //cout << i << " " << j << " " << i << " " << *it << "\n";
            }
            s.insert(j);
        }
        for (int j = 0; j < m; j++) b[j] = make_pair(a[i][j], -j);
        sort(b.begin(), b.end());        
        s.clear();
        for (int k = b.size()-1; k >= 0; k--) {
            int j = -b[k].second;
            auto it = s.lower_bound(j);
            if (it != s.begin()) {
                --it;
                if (abs(*it - j) > 1) row[i*m + j - 1].push_back(*it + 1); 
             //   if (i == 1 && j == 1) cout << "!! " << *it << "\n";
               // cout << i << " " << j << " " << i << " " << *it << "\n";
            }
            s.insert(j);
        }
    }
    //col edges
    for (int i = 0; i < m; i++) {
        vector<pair<int,int>> b(n);
        for (int j = 0; j < n; j++) b[j] = make_pair(a[j][i], j);
        sort(b.begin(), b.end());
        set<int> s;
        for (int k = b.size()-1; k >= 0; k--) {
            int j = b[k].second;
            auto it = s.lower_bound(j);
            if (it != s.end()) {
                if (abs(*it - j) > 1) col[(j+1)*m + i].push_back(*it-1);  
                //cout << j << " " << i << " " << *it << " " << i << "\n";
            }
            s.insert(j);
        }
        for (int j = 0; j < n; j++) b[j] = make_pair(a[j][i], -j);
        sort(b.begin(), b.end());        
        s.clear();
        for (int k = b.size()-1; k >= 0; k--) {
            int j = -b[k].second;
            auto it = s.upper_bound(j);
            if (it != s.begin()) {
                --it;
                if (abs(*it - j) > 1) col[(j-1)*m + i].push_back(*it+1); 
                //cout << j << " " << i << " " << *it << " " << i << "\n";
            }
            s.insert(j);
        }
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (auto B: row[i*m + j]) {
                for (auto C: col[i*m + j]) {
                    //if (abs(C-i) <= 1 || abs(B-j) <= 1) continue;
                    if (a[C][B] < a[i][j] || (a[C][B] == a[i][j] && (make_pair(C,B) < make_pair(i,j)))) continue;
                    // if (j > B) swap(j,B);
                    // if (i > C) swap(i,C);
                    bool works = true;
                    for (int y = min(j,B); y <= max(j,B); y++) {
                        if (!inside(col[i*m + y], C) && !inside(col[C*m + y] , i)) {
                            works = false;
                            break;
                        }
                    }
                    for (int x = min(i,C); x <= max(i,C); x++) {
                        if (!inside(row[x*m + j] , B) && !inside(row[x*m + B] , j)) {
                            works = false;
                            break;
                        }
                    }
                    // bool BD = inside(col[i*m + B], C) || inside(col[C*m + B] , i);
                    // bool CD = inside(row[C*m + j] , B) || inside(row[C*m + B] , j);
                    if (works) {
                        //for (int )
                        //cout << i << " " << j << " " << C << " " << B << "\n";
                        cnt++;
                    }
                }
            }
        }
    }

	return cnt;
}

• 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