Submission #500524

#	Time	Username	Problem	Language	Result	Execution time	Memory
500524		InternetPerson10	Rectangles (IOI19_rect)	C++17	49 / 100	1799 ms	142876 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

const int SMALL = -2;
const int BIG = 1234567890;

struct ordered_set { // This is actually just a fenwick tree
    vector<int> nums;
    int size = 4096;
    int ct = 0;
    ordered_set() {
        nums.resize(size+1);
    }
    void insert(int n) {
        ct++;
        n++;
        while(n <= size) {
            nums[n]++;
            n += (n & (-n));
        }
    }
    void erase(int n) {
        ct--;
        n++;
        while(n <= size) {
            nums[n]--;
            n += (n & (-n));
        }
    }
    int count(int n) {
        int ans = 0;
        while(n) {
            ans += nums[n];
            n -= (n & (-n));
        }
        return ct - ans;
    }
};

long long count_rectangles(vector<vector<int>> a) {
    // Idea: consider "good" segments, where the ones to the left and to the right are bigger
    // It turns out there are O(n) such subsegments in a segment with n elements
    // Thus, in a "good" rectangle, each row and column must be a good segment
    // Fix the upper left corner of a rectangle, consider some particular segment
    //  which starts at this square, WLOG it is horizontal
    // The number of rectangles that "use" this segment is equal to the number of
    //  vertical segments that all have the same length, which cover the same width
    // You can do this with like, sweep line
    int n = a.size();
    int m = a[0].size();
    if(min(n, m) <= 2) return 0;
    vector<vector<vector<pair<int, int>>>> ps(n);
    vector<pair<int, int>> v;
    v.resize(m);
    for(int i = 0; i < n; i++) {
        ps[i].resize(m);
        for(int j = 0; j < m; j++) {
            v[j] = {a[i][j], -j};
        }
        sort(v.rbegin(), v.rend());
        set<int> s;
        s.insert(SMALL);
        s.insert(BIG);
        int g = -1;
        for(int j = 0; j < m; j++) {
            v[j].second *= -1;
            auto it1 = s.lower_bound(v[j].second);
            auto it2 = it1;
            it1--;
            s.insert(v[j].second);
            if(g != -1) {
                if(g == (*it2) && v[j].first == v[j-1].first) {
                    ps[i][v[j-1].second+1].pop_back();
                }
            }
            g = (*it2);
            if(*it1 != SMALL && *it1 + 1 != v[j].second) ps[i][(*it1)+1].push_back({1, v[j].second-1});
            if(*it2 != BIG && v[j].second + 1 != *it2) ps[i][v[j].second+1].push_back({1, (*it2)-1});
            else g = -1;
        }
        set<int>().swap(s);
    }
    v.resize(n);
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            v[j] = {a[j][i], -j};
        }
        sort(v.rbegin(), v.rend());
        set<int> s;
        s.insert(SMALL);
        s.insert(BIG);
        int g = -1;
        for(int j = 0; j < n; j++) {
            v[j].second *= -1;
            auto it1 = s.lower_bound(v[j].second);
            auto it2 = it1;
            it1--;
            s.insert(v[j].second);
            if(g != -1) {
                if(g == (*it2) && v[j].first == v[j-1].first) ps[v[j-1].second+1][i].pop_back();
            }
            g = (*it2);
            if(*it1 != SMALL && *it1 + 1 != v[j].second) ps[(*it1)+1][i].push_back({-1, v[j].second-1});
            if(*it2 != BIG && v[j].second + 1 != *it2) ps[v[j].second+1][i].push_back({-1, (*it2)-1});
            else g = -1;
        }
        set<int>().swap(s);
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            for(auto &p : ps[i][j]) {
                swap(p.first, p.second);
                // cout << i << ' ' << j << ' ' << p.first << ' ' << p.second << '\n';
            }
            sort(ps[i][j].begin(), ps[i][j].end());
        }
    }
    for(int i = n-2; i > 0; i--) {
        for(int j = m-2; j > 0; j--) {
            for(auto &p : ps[i][j]) {
                if(p.second > 0) { // strokes horizontal
                    pair<int, int> pe = {p.first, 0};
                    auto it = lower_bound(ps[i+1][j].begin(), ps[i+1][j].end(), pe);
                    if(it != ps[i+1][j].end()) {
                        auto pa = (*it);
                        // cout << pa.first << ' ' << pa.second << '\n';
                        if(pa.first == p.first && pa.second > 0) {
                            p.second += pa.second;
                        }
                    }
                }
                else { // strokes vertical
                    pair<int, int> pe = {p.first, -BIG};
                    auto it = lower_bound(ps[i][j+1].begin(), ps[i][j+1].end(), pe);
                    if(it != ps[i][j+1].end()) {
                        auto pa = (*it);
                        if(pa.first == p.first && pa.second < 0) {
                            p.second += pa.second;
                        }
                    }
                }
            }
        }
    }
    if(max(n, m) >= 1000) return -1;
    long long ans = 0;
    for(int i = 1; i < n-1; i++) {
        for(int j = 1; j < m-1; j++) {
            vector<pair<pair<int, int>, int>> pts;
            for(auto p : ps[i][j]) {
                // cout << i << ' ' << j << ' ' << p.first << ' ' << p.second << '\n';
                if(p.second > 0) pts.push_back({{i-1+p.second, -p.first}, 1});
                else pts.push_back({{p.first, -j+1+p.second}, -1});
            }
            sort(pts.begin(), pts.end());
            ordered_set s;
            for(auto p : pts) {
                // cout << p.first.first << ' ' << p.first.second << ' ' << p.second << '\n';
                if(p.second == 1) {
                    ans += s.count(abs(p.first.second));
                }
                else {
                    s.insert(abs(p.first.second));
                }
            }
            for(auto p : pts) {
                if(p.second == -1) {
                    s.erase(abs(p.first.second));
                }
            }
            // cout << ans << '\n';
        }
    }
    return ans;
}

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