제출 #500581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500581		InternetPerson10	Rectangles (IOI19_rect)	C++17	100 / 100	3315 ms	402600 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;
    for(int i = 0; i < n; i++) {
        ps[i].resize(m);
        v.push_back({BIG, -1});
        for(int j = 0; j < m; j++) {
            while(v.back().first < a[i][j]) {
                if(j - v.back().second > 1) ps[i][v.back().second+1].push_back({1, j-1});
                while(v.size() >= 2) {
                    if(v.back().first == v[v.size()-2].first) v.pop_back();
                    else break;
                }
                v.pop_back();
            }
            if(j - v.back().second > 1 && v.size() > 1) ps[i][v.back().second+1].push_back({1, j-1});
            v.push_back({a[i][j], j});
        }
        vector<pair<int, int>>().swap(v);
    }
    for(int i = 0; i < m; i++) {
        v.push_back({BIG, -1});
        for(int j = 0; j < n; j++) {
            while(v.back().first < a[j][i]) {
                if(j - v.back().second > 1) ps[v.back().second+1][i].push_back({-1, j-1});
                while(v.size() >= 2) {
                    if(v.back().first == v[v.size()-2].first) v.pop_back();
                    else break;
                }
                v.pop_back();
            }
            if(j - v.back().second > 1 && v.size() > 1) ps[v.back().second+1][i].push_back({-1, j-1});
            v.push_back({a[j][i], j});
        }
        vector<pair<int, int>>().swap(v);
    }
    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;
                        }
                    }
                }
            }
        }
    }
    long long ans = 0;
    ordered_set s;
    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());
            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: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 28 / 28