Submission #829371

#	Time	Username	Problem	Language	Result	Execution time	Memory
829371		kamelfanger83	Rectangles (IOI19_rect)	C++17	Compilation error	0 ms	0 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<int>, MAXN>, MAXN> hors, verts;
vector<vector<int>> aG;
array<array<vector<pair<int, int>>, MAXN>, MAXN> hpossibs, vpossibs;

void line(int i){
    vector<int> records = {0};
    for (int j = 1; j < m; ++j) {
        while (!records.empty() && aG[i][j] >= aG[i][records.back()]){
            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) 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) {
        while (!records.empty() && aG[i][j] >= aG[records.back()][j]){
            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) verts[records.back() + 1][j].push_back(i - records.back() - 1);
        records.push_back(i);
    }
}

long long count_rectangles(vector<vector<int>> a){
    n = a.size(); m = a[0].size(); 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 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 cs++;
            }
            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;
}


int main(){
    cerr << count_rectangles({{10, 10, 10, 10, 10},
    {10, 1, 2, 3, 4},
    {10, 2, 3, 4, 5},
    {10, 3, 4, 5, 6},
    {10, 4, 5, 6, 7},
    {10, 5, 6, 7, 8},
                              {10, 6, 7, 8, 9}}) << "\n";
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc4Gk2yy.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccDl3GJA.o:rect.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status