Submission #373873

#	Time	Username	Problem	Language	Result	Execution time	Memory
373873		ijxjdjd	Rectangles (IOI19_rect)	C++14	Compilation error	0 ms	0 KiB

rect

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

#define f first
#define s second


const int MAXN = 2500;
using ll = long long;
std::vector<int> right[MAXN][MAXN];
std::vector<int> down[MAXN][MAXN];
std::vector<bool> usedRight[MAXN][MAXN];
std::vector<bool> usedDown[MAXN][MAXN];
std::vector<std::pair<int, int>> rightP[MAXN][MAXN];
std::vector<std::pair<int, int>> downP[MAXN][MAXN];
std::vector<std::vector<int>> a;
int N, M;
int btsearch(std::vector<int>& vec, int v) {
    if (vec.size()==0) {
        return -1;
    }
    int low = 0;
    int high = int(vec.size())-1;
    while (low < high) {
        int mid = (low + high)/2;
        if (vec[mid] <= v) {
            low = mid;
        }
        else if (vec[mid]) {
            high = mid-1;
        }
    }
    if (vec[low] == v) {
        return low;
    }
    return -1;
}
void setPairs() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int id = 0;
            for (int p : right[i][j]) {
                if (!usedRight[i][j][id]) {
                    int u = i;
                    while (true) {
                        int k = btsearch(right[u+1][j], p);
                        if (k == -1) {
                            break;
                        }
                        else {
                            usedRight[u+1][j][k] = true;
                        }
                        u++;
                    }
                    int lst = u;
                    while (u >= i) {
                        rightP[u][j].push_back({lst, p});
                        u--;
                    }
                }
                id++;
            }
        }
    }
    for (int j = 0; j < M; j++) {
        for (int i = 0; i < N; i++) {
            int id = 0;
            for (int p : down[i][j]) {
                if (!usedDown[i][j][id]) {
                    int u = j;
                    while (true) {
                        int k = btsearch(down[i][u+1], p);
                        if (k == -1) {
                            break;
                        }
                        else {
                            usedDown[i][u+1][k] = true;
                        }
                        u++;
                    }
                    int lst = u;
                    while (u >= j) {
                        downP[i][u].push_back({p, lst});
                        u--;
                    }
                }
                id++;

            }
        }
    }
}
void getIntervals() {
//    for (int i = 1; i < N-1; i++) {
//        for (int j = 1; j < M-1; j++) {
//            int mx = 0;
//            for (int k = j; k < M-1; k++) {
//                mx = std::max(mx, a[i][k]);
//                if (a[i][j-1] > mx && a[i][k+1] > mx) {
//                    right[i][j].insert(k);
//                }
//            }
//        }
//    }
//    for (int j = 1; j < M-1; j++) {
//        for (int i = 1; i < N-1; i++) {
//            int mx = 0;
//            for (int k = i; k < N-1; k++) {
//                mx = std::max(mx, a[k][j]);
//                if (a[i-1][j] > mx && a[k+1][j] > mx) {
//                    down[i][j].insert(k);
//                }
//            }
//        }
//    }
    for (int i = 1; i < N-1; i++) {
        std::stack<std::pair<int, int>> st;
        st.push({a[i][0], 0});
        for (int j = 1; j < M; j++) {
            bool eq = false;
            while (st.size() && a[i][j] >= st.top().f) {
                if (st.top().s + 1 <= j-1) {
//                    if (!right[i][st.top().s+1].count(j-1)) {
//                        std::cout << "I inside"<< '\n';
//                    }
                    right[i][st.top().s+1].push_back(j-1);
                }
                eq = (a[i][j] == st.top().f);
                st.pop();
            }
            if (!eq) {
                if (st.size() && st.top().s + 1 <= j-1) {
//                    if (!right[i][st.top().s+1].count(j-1)) {
//                        std::cout << "I out"<< '\n';
//                    }
                    right[i][st.top().s+1].push_back(j-1);
                }
            }
            st.push({a[i][j], j});
        }
    }
    for (int j = 1; j < M-1; j++) {
        std::stack<std::pair<int, int>> st;
        st.push({a[0][j], 0});
        for (int i = 1; i < N; i++) {
            bool eq = false;
            while (st.size() && a[i][j] >= st.top().f) {
                if (st.top().s + 1 <= i-1) {
//                    if (!down[st.top().s+1][j].count(i-1)) {
//                        std::cout << st.top().s+1 << " " << j << " " << i-1 <<'\n';
//                    }
                    down[st.top().s+1][j].push_back(i-1);
                }
                eq = (a[i][j] == st.top().f);
                st.pop();
            }
            if (!eq) {
                if (st.size() && st.top().s + 1 <= i-1) {
//                    if (!down[st.top().s+1][j].count(i-1)) {
//                        std::cout << st.top().s+1 << " " << j << " " << i-1 <<'\n';
//                    }
                    down[st.top().s+1][j].push_back(i-1);
                }
            }
            st.push({a[i][j], i});
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            usedDown[i][j].resize(down[i][j].size(), false);
            usedRight[i][j].resize(right[i][j].size(), false);
            sort(down[i][j].begin(), down[i][j].end());
            sort(right[i][j].begin(), right[i][j].end());
        }
    }
    setPairs();
}
int fen[MAXN];
void add(int val, int id) {
    for (;id<MAXN;id=(id|(id+1))) {
        fen[id]+=val;
    }
}
int sm(int r) {
    int rs = 0;
    for (;r >= 0; r=(r&(r+1)) - 1) {
        rs += fen[r];
    }
    return rs;
}
int sm(int l, int r) {
    return sm(r) - sm(l-1);
}
long long count_rectangles(std::vector<std::vector<int> > board) {
    a = board;
    N = a.size();
    M = a[0].size();
    a.resize(N, vector<int>(M, 0));
    if (N <= 2 || M <= 2) {
        return 0;
    }
for (int i = 1; i < N-1; i++) {
        std::stack<std::pair<int, int>> st;
        st.push({a[i][0], 0});
        for (int j = 1; j < M; j++) {
            bool eq = false;
            while (st.size() && a[i][j] >= st.top().f) {
                if (st.top().s + 1 <= j-1) {
//                    if (!right[i][st.top().s+1].count(j-1)) {
//                        std::cout << "I inside"<< '\n';
//                    }
                    right[i][st.top().s+1].push_back(j-1);
                }
                eq = (a[i][j] == st.top().f);
                st.pop();
            }
            if (!eq) {
                if (st.size() && st.top().s + 1 <= j-1) {
//                    if (!right[i][st.top().s+1].count(j-1)) {
//                        std::cout << "I out"<< '\n';
//                    }
                    right[i][st.top().s+1].push_back(j-1);
                }
            }
            st.push({a[i][j], j});
        }
    }
    for (int j = 1; j < M-1; j++) {
        std::stack<std::pair<int, int>> st;
        st.push({a[0][j], 0});
        for (int i = 1; i < N; i++) {
            bool eq = false;
            while (st.size() && a[i][j] >= st.top().f) {
                if (st.top().s + 1 <= i-1) {
//                    if (!down[st.top().s+1][j].count(i-1)) {
//                        std::cout << st.top().s+1 << " " << j << " " << i-1 <<'\n';
//                    }
                    down[st.top().s+1][j].push_back(i-1);
                }
                eq = (a[i][j] == st.top().f);
                st.pop();
            }
            if (!eq) {
                if (st.size() && st.top().s + 1 <= i-1) {
//                    if (!down[st.top().s+1][j].count(i-1)) {
//                        std::cout << st.top().s+1 << " " << j << " " << i-1 <<'\n';
//                    }
                    down[st.top().s+1][j].push_back(i-1);
                }
            }
            st.push({a[i][j], i});
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            usedDown[i][j].resize(down[i][j].size(), false);
            usedRight[i][j].resize(right[i][j].size(), false);
            sort(down[i][j].begin(), down[i][j].end());
            sort(right[i][j].begin(), right[i][j].end());
        }
    }
    setPairs();
    ll res = 0;
//    std::cout << sizeof(right) + sizeof(down) + sizeof(rightP) + sizeof(downP) + sizeof(usedRight) + sizeof(usedDown) << '\n';
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            std::sort(rightP[i][j].begin(), rightP[i][j].end());
            std::sort(downP[i][j].begin(), downP[i][j].end());
            int u = 0;
            for (auto& p : rightP[i][j]) {
                while (u < downP[i][j].size() && downP[i][j][u].f <= p.f) {
                    add(1, downP[i][j][u].s);
                    u++;
                }
                res += sm(p.s, MAXN-1);
//                for (auto& u : downP[i][j]) {
//                    if (u.f <= p.f && u.s >= p.s) {
//                        res++;
//                    }
//                }
            }
//            memset(fen, 0, sizeof(fen));
            while (--u>= 0) {
                add(-1, downP[i][j][u].s);
            }
        }
    }
    return res;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:198:17: error: 'vector' was not declared in this scope; did you mean 'std::vector'?
  198 |     a.resize(N, vector<int>(M, 0));
      |                 ^~~~~~
      |                 std::vector
In file included from /usr/include/c++/9/vector:67,
                 from rect.h:5,
                 from rect.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:386:11: note: 'std::vector' declared here
  386 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
rect.cpp:198:24: error: expected primary-expression before 'int'
  198 |     a.resize(N, vector<int>(M, 0));
      |                        ^~~
rect.cpp:271:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  271 |                 while (u < downP[i][j].size() && downP[i][j][u].f <= p.f) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~