Submission #829525

#	Time	Username	Problem	Language	Result	Execution time	Memory
829525		kamelfanger83	Rectangles (IOI19_rect)	C++17	100 / 100	2876 ms	782076 KiB

rect

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <set>

using namespace std;

#define MAXN 2500
int n, m;
array<array<vector<int16_t>, MAXN>, MAXN> hors, verts;
vector<vector<signed>> aG;

void line(int i){
    vector<int> records = {0};
    for (int j = 1; j < m; ++j) {
        bool rsame = false;
        while (!records.empty() && aG[i][j] >= aG[i][records.back()]){
            if (aG[i][j] == aG[i][records.back()]) rsame = true;
            if (records.back() + 1 < j) hors[i][records.back() + 1].push_back(j - records.back() - 1);
            records.pop_back();
        }
        if (!records.empty() && records.back() + 1 < j && !rsame) hors[i][records.back() + 1].push_back(j - records.back() - 1);
        records.push_back(j);
    }
}

void column(int j){
    vector<int> records = {0};
    for (int i = 1; i < n; ++i) {
        bool rsame = false;
        while (!records.empty() && aG[i][j] >= aG[records.back()][j]){
            if (aG[i][j] == aG[records.back()][j]) rsame = true;
            if (records.back() + 1 < i) verts[records.back() + 1][j].push_back(i - records.back() - 1);
            records.pop_back();
        }
        if (!records.empty() && records.back() + 1 < i && !rsame) verts[records.back() + 1][j].push_back(i - records.back() - 1);
        records.push_back(i);
    }
}

long long count_rectangles(vector<vector<signed>> a){
    n = a.size(); m = a[0].size(); swap(aG, a);
    for (int i = 0; i < n; ++i) line(i);
    for (int j = 0; j < m; ++j) column(j);
    int ans = 0;
    array<vector<pair<int, int>>, MAXN> lastr;
    for (int j = m - 2; j >= 0; --j) {
        array<vector<pair<int, int>>, MAXN> tr;
        vector<pair<int, int>> down;
        for (int i = n - 2; i >= 0; --i) {
            sort(verts[i][j].begin(), verts[i][j].end());
            auto itt = lastr[i].begin();
            auto cs = verts[i][j].begin();
            while (itt != lastr[i].end() && cs != verts[i][j].end()){
                if ((*itt).second == *cs) tr[i].emplace_back((*itt++).first + 1, *cs++);
                else if ((*itt).second < *cs) itt++;
                else tr[i].emplace_back(1, *cs++);;
            }
            while (cs != verts[i][j].end()) tr[i].emplace_back(1, *cs++);
            vector<pair<int, int>> here;
            sort(hors[i][j].begin(), hors[i][j].end());
            itt = down.begin();
            cs = hors[i][j].begin();
            while (itt != down.end() && cs != hors[i][j].end()){
                if ((*itt).first == *cs) here.emplace_back(*cs++, (*itt++).second + 1);
                else if ((*itt).first < *cs) itt++;
                else here.emplace_back(*cs++, 1);
            }
            while (cs != hors[i][j].end()) here.emplace_back(*cs++, 1);
            multiset<int> hlimits;
            vector<pair<int, int>> vcopy = tr[i];
            sort(vcopy.begin(), vcopy.end());
            auto hor = here.begin();
            auto ver = vcopy.begin();
            while (hor != here.end() && ver != vcopy.end()){
                if ((*hor).first <= (*ver).first) hlimits.insert((*hor++).second);
                else ans += distance(hlimits.lower_bound((*ver++).second), hlimits.end());
            }
            while (ver != vcopy.end()) ans += distance(hlimits.lower_bound((*ver++).second), hlimits.end());
            swap(down, here);
        }
        swap(lastr, tr);
    }
    return ans;
}

/*
signed main(){
    cerr << count_rectangles({{10, 9, 8, 9, 10},
                              {9 , 8, 7, 8, 9 },
                              {8 , 7, 6, 7, 8 },
                              {7 , 6, 5, 6, 7 },
                              {8 , 7, 6, 7, 8 },
                              {9 , 8, 7, 8, 9 },
                              {10, 9, 8, 9, 10}}) << "\n";
    return 0;
}*/

• 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