Submission #829510

#	Time	Username	Problem	Language	Result	Execution time	Memory
829510		kamelfanger83	Rectangles (IOI19_rect)	C++17	72 / 100	1685 ms	1048576 KiB

rect

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

using namespace std;

struct Node {
    int sum = 0, l = -1, r = -1;
};

struct SparseSeg{
    vector<Node> cache;
    void insert(int l, int r, int i, int v){
        //if (r <= v || v <= l) return;
        if (l + 1 == r) {
            ++cache[i].sum;
            return;
        }
        int m = l + (r-l)/2;
        if (v >= m) {
            if (cache[i].r == -1) {
                cache[i].r = cache.size();
                cache.push_back({});
            }
            insert(m, r, cache[i].r, v);
        }
        else {
            if (cache[i].l == -1) {
                cache[i].l = cache.size();
                cache.push_back({});
            }
            insert(l, m, cache[i].l, v);
        }
        ++cache[i].sum;
    }
    int postfixsum (int l, int r, int i, int ii){
        if (l + 1 == r) return cache[i].sum;
        int m = l + (r-l)/2;
        if (ii < m) {
            int ret = 0;
            if (cache[i].l != -1) ret += postfixsum(l, m, cache[i].l, ii);
            if (cache[i].r != -1) ret += cache[cache[i].r].sum;
            return ret;
        }
        else {
            if (cache[i].r != -1) return postfixsum(m, r, cache[i].r, ii);
            return 0;
        }
    }
};

#define MAXN 2500
int n, m;
array<array<vector<short>, MAXN>, MAXN> hors, verts;
vector<vector<signed>> aG;
array<array<vector<pair<short, short>>, MAXN>, MAXN> hpossibs, vpossibs;

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);
    for (int j = m - 2; j >= 0; --j) {
        for (int i = 0; i < n; ++i) {
            sort(verts[i][j].begin(), verts[i][j].end());
            auto itt = vpossibs[i][j+1].begin();
            auto cs = verts[i][j].begin();
            while (itt != vpossibs[i][j+1].end() && cs != verts[i][j].end()){
                if ((*itt).second == *cs) vpossibs[i][j].emplace_back((*itt++).first + 1, *cs++);
                else if ((*itt).second < *cs) itt++;
                else vpossibs[i][j].emplace_back(1, *cs++);;
            }
            while (cs != verts[i][j].end()) vpossibs[i][j].emplace_back(1, *cs++);
        }
    }
    for (int i = n - 2; i >= 0; --i) {
        for (int j = 0; j < m; ++j) {
            sort(hors[i][j].begin(), hors[i][j].end());
            auto itt = hpossibs[i + 1][j].begin();
            auto cs = hors[i][j].begin();
            while (itt != hpossibs[i + 1][j].end() && cs != hors[i][j].end()){
                if ((*itt).first == *cs) hpossibs[i][j].emplace_back(*cs++, (*itt++).second + 1);
                else if ((*itt).first < *cs) itt++;
                else hpossibs[i][j].emplace_back(*cs++, 1);
            }
            while (cs != hors[i][j].end()) hpossibs[i][j].emplace_back(*cs++, 1);
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            //SparseSeg seg;
            //seg.cache.push_back({});
            multiset<int> hlimits;
            sort(vpossibs[i][j].begin(), vpossibs[i][j].end());
            auto hor = hpossibs[i][j].begin();
            auto ver = vpossibs[i][j].begin();
            while (hor != hpossibs[i][j].end() && ver != vpossibs[i][j].end()){
                if ((*hor).first <= (*ver).first) hlimits.insert((*hor++).second);
                else ans += distance(hlimits.lower_bound((*ver++).second), hlimits.end());
            }
            while (ver != vpossibs[i][j].end()) ans += distance(hlimits.lower_bound((*ver++).second), hlimits.end());
        }
    }
    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: 0 / 28