Submission #212041

#	Time	Username	Problem	Language	Result	Execution time	Memory
212041		anonymous	Rectangles (IOI19_rect)	C++14	100 / 100	3038 ms	974560 KiB

rect

#include "rect.h"
#include<unordered_set>
#include<vector>
#include<algorithm>
#include<utility>
#define MAXN 2505
using namespace std;
int N,M,A[MAXN][MAXN], Prev[MAXN][MAXN][2];
vector<pair<int,int> > Hor[MAXN][MAXN], Vert[MAXN][MAXN];
vector<pair<int,int>> HorM[MAXN], VertM[MAXN]; 
vector<pair<int,int> > S;

class fenwick {
    int ft[MAXN + 5];
public:
    void add(int v, int p) {
        for (int i=p; i<=MAXN; i+=i&(-i)) {ft[i]+=v;}
    }
    int ask(int p) {
        int res = 0;
        for (int i=p; i>0; i-=i&(-i)) {res+=ft[i];}
        return(res);
    }
} BIT;

void pairs() {
    for (int i=1; i<=N; i++) { //init horizontal
        while (S.size()) {S.pop_back();}
        for (int j=1; j<=M; j++) {
            bool same = false;
            while(S.size() && S.back().first <= A[i][j]) {
                if (A[i][j] == S.back().first) {same=true;}
                if (j - S.back().second > 1) {HorM[i].push_back({S.back().second, j});}
                S.pop_back();
            }
            if (!same && S.size() && j - S.back().second > 1) {HorM[i].push_back({S.back().second, j});}
            S.push_back({A[i][j], j});
        }
    }
    for (int j=1; j<=M; j++) {
        while (S.size()) {S.pop_back();}
        for (int i=1; i<=N; i++) {
            bool same = false;
            while (S.size() && S.back().first <= A[i][j]) {
                if (A[i][j] == S.back().first) {same=true;}
                if (i - S.back().second > 1) {VertM[j].push_back({S.back().second,i});}
                S.pop_back();
            }
            if (!same && S.size() && i - S.back().second > 1) {VertM[j].push_back({S.back().second,i});}
            S.push_back({A[i][j], i});
        }
    }
    for (int i=N; i>=1; i--) {
        for (int k=0; k<HorM[i].size(); k++) {
            pair <int,int> p = HorM[i][k];
            if (Prev[p.first][p.second][0] != i+1) {
                Prev[p.first][p.second][1] = i;
            }
            Prev[p.first][p.second][0] = i;
            Hor[i][p.first].push_back({p.second, Prev[p.first][p.second][1]});
        }
    }
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            Prev[i][j][0] = Prev[i][j][1] = 0;
        }
    }
    for (int j=M; j>=1; j--) {
        for (int k=0; k<VertM[j].size(); k++) {
            pair <int,int> p = VertM[j][k];
            if (Prev[p.first][p.second][0] != j+1) {
                Prev[p.first][p.second][1] = j;
            }
            Prev[p.first][p.second][0] = j;
            Vert[p.first][j].push_back({Prev[p.first][p.second][1], p.second});
        }
    }
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            sort(Hor[i][j].begin(), Hor[i][j].end());
            sort(Vert[i][j].begin(), Vert[i][j].end());
        }
    }
}

long long count_rectangles(vector<vector<int> > a) {
    long long ans = 0;
    N = a.size(), M = a[0].size();
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            A[i+1][j+1]=a[i][j]; //zero index
        }
    }
    pairs();
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            int pt1 = Hor[i+1][j].size()-1, pt2 = Vert[i][j+1].size()-1; 
            while (pt1 >= 0 || pt2 >= 0) {
                if (pt1 == -1 || (pt2 >= 0 && Hor[i+1][j][pt1].first <= Vert[i][j+1][pt2].first+1)) {
                    BIT.add(1, Vert[i][j+1][pt2].second);
                    pt2--;
                } else {
                    ans += (long long) BIT.ask(Hor[i+1][j][pt1].second+1) - BIT.ask(i+1);
                    pt1--;
                }
            }
            for (auto v: Vert[i][j+1]) {
                BIT.add(-1, v.second);
            }
        }
    }
    return(ans);
}

Compilation message (stderr)

rect.cpp: In function 'void pairs()':
rect.cpp:54:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int k=0; k<HorM[i].size(); k++) {
                       ~^~~~~~~~~~~~~~~
rect.cpp:69:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int k=0; k<VertM[j].size(); k++) {
                       ~^~~~~~~~~~~~~~~~

• 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