Submission #373848

#	Time	Username	Problem	Language	Result	Execution time	Memory
373848		ijxjdjd	Rectangles (IOI19_rect)	C++14	0 / 100	875 ms	979344 KiB

rect

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

#define f first
#define s second
const int MAXN = 2500;
using ll = long long;
std::unordered_set<int> right[MAXN][MAXN];
std::unordered_set<int> down[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;
void setPairs() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int p : right[i][j]) {
                int u = i;
                while (right[u+1][j].count(p)) {
                    u++;
                }
                int lst = u;
                while (u >= i) {
                    rightP[u][j].push_back({lst, p});
                    if (u != i) {
                        right[u][j].erase(p);
                    }
                    u--;
                }
            }
        }
    }
    for (int j = 0; j < M; j++) {
        for (int i = 0; i < N; i++) {
            for (int p : down[i][j]) {
                int u = j;
                while (down[i][u+1].count(p)) {
                    u++;
                }
                int lst = u;
                while (u >= j) {
                    downP[i][u].push_back({p, lst});
                    if (u != j) {
                        down[i][u].erase(p);
                    }
                    u--;
                }
            }
        }
    }
}
void getIntervals() {

    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++) {
            while (st.size() && a[i][j] > st.top().f) {
                if (st.top().s + 1 <= j-1) {
                    right[i][st.top().s+1].insert(j-1);
                }
                st.pop();
            }
            if (st.size() && st.top().s + 1 <= j-1) {
                right[i][st.top().s+1].insert(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++) {
            while (st.size() && a[i][j] > st.top().f) {
                if (st.top().s + 1 <= i-1) {
                    down[st.top().s+1][j].insert(i-1);
                }
                st.pop();
            }
            if (st.size() && st.top().s + 1 <= i-1) {
                down[st.top().s+1][j].insert(i-1);
            }
            st.push({a[i][j], i});
        }
    }
    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();
    if (N == 1 || M == 1) {
        return 0;
    }
    getIntervals();
    ll res = 0;
    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);
            }
            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:119: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]
  119 |                 while (u < downP[i][j].size() && downP[i][j][u].f <= p.f) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28