제출 #1069222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1069222		RaresFelix	Rectangles (IOI19_rect)	C++17	0 / 100	185 ms	441172 KiB

rect

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;

const int MN = 2500;

struct DSU {
    vi e, mi, ma;
    DSU(int n) : e(n, -1), mi(n), ma(n) {
        iota(mi.begin(), mi.end(), 0);
        iota(ma.begin(), ma.end(), 0);
    }

    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }

    void join(int u, int v) {
        u = repr(u); v = repr(v);
        if(u == v) return;
        if(e[u] >= e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
        mi[u] = min(mi[u], mi[v]);
        ma[u] = max(ma[u], ma[v]);
    }

    ii get_seg(int u) {
        u = repr(u);
        return ii{mi[u], ma[u]};
    }
};

vector<ii> Perechi[MN][MN];

vector<pair<ii, ii> > get_linii(vector<vi> &a) {
    int n = int(a.size()), m = int(a[0].size());
    for(int i = 1; i + 1 < n; ++i) {
        vector<ii> ord;
        for(int j = 0; j < m; ++j)
            ord.push_back({a[i][j], j});
        sort(ord.begin(), ord.end());

        DSU Poz(m);
        vector<bool> on(m, false);

        int p2 = 0;
        for(int j = 0; j < m; ++j) {
            auto [v, p] = ord[j];

            while(p2 < m && ord[p2].first < v) {
                int u = ord[p2].second;
                on[u] = true;
                if(u && on[u - 1]) Poz.join(u, u - 1);
                if(u + 1 < m && on[u + 1]) Poz.join(u, u + 1);
               ++p2;
           }

            if(p && on[p - 1]) {
                auto [mi, ma] = Poz.get_seg(p - 1);
                if(mi)
                    Perechi[i][p].push_back({mi - 1, p});
            }
            if(p + 1 < n && on[p + 1]) {
                auto [mi, ma] = Poz.get_seg(p + 1);
                if(ma + 1 < n) {
                    Perechi[i][p].push_back({p, ma + 1});
                    //Perechi[i].insert(p * m + ma + 1);
                }
            }

        }
    }
    vector<pair<ii, ii> > Re;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            for(auto [st, dr] : Perechi[i][j]) {
                int p = i;
                int ok = 1;
                if(!i) {
                    for(auto [s1, d1]: Perechi[p - 1][st])
                        if(s1 == st && d1 == dr) ok = 0;
                    for(auto [s1, d1]: Perechi[p - 1][dr])
                        if(s1 == st && d1 == dr) ok = 0;
                }
                if(!ok) continue; // nu suntem primii
                while(p + 1 < n) {
                    int ok = 0;
                    for(auto [s1, d1]: Perechi[p][st])
                        if(s1 == st && d1 == dr) ok = 1;
                    for(auto [s1, d1]: Perechi[p][dr])
                        if(s1 == st && d1 == dr) ok = 1;
                    if(ok)
                        ++p;
                    else break;
                }
                Re.push_back({{i - 1, p + 1}, {st, dr}});
            }
        }
    }
    return Re;
}

namespace AIB {
    const int MN = 2501;
    int V[MN];

    void update(int p, int v) {
        ++p;
        while(p < MN) {
            V[p] += v;
            p += p & -p;
        }
    }

    int query(int p) {
        ++p;
        if(p < 0) return 0;
        int re = 0;
        while(p) {
            re += V[p];
            p -= p & -p;
        }
        return re;
    }
};
vector<ii> LinV[MN][MN];
vector<ii> LinH[MN][MN];

ll count_rectangles(vector<vi> a) {
    int n = int(a.size()), m = int(a[0].size());
    vector<vi> b(m, vi(n, 0));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            b[j][i] = a[i][j];
    auto V = get_linii(a), H = get_linii(b);
    return 0;
    for(auto &[x, y] : H) swap(x, y);
    auto inclus = [&](ii a, ii b) {
        ///b inclus in a
        return b.first >= a.first && b.second <= a.second;
    };
    int re = 0;
    for(auto [x, y] : V) {
        for(int i = x.first; i <= x.second; ++i) {
            LinV[i][y.second].push_back({i - x.first, y.second - y.first});
        }
    }
    for(auto [x, y] : H) {
        for(int j = y.first; j <= y.second; ++j) {
            LinH[x.second][j].push_back({x.second - x.first, j - y.first});
        }
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            int l1 = (int)LinH[i][j].size(), l2 = (int)LinV[i][j].size();
            sort(LinH[i][j].begin(), LinH[i][j].end());
            sort(LinV[i][j].begin(), LinV[i][j].end());
            int p = 0;
            for(auto [xv, yv] : LinV[i][j]) {
                while(p < l1 && LinH[i][j][p].first <= xv) {
                    AIB::update(m - LinH[i][j][p].second - 1, 1);
                    ++p;
                }
                re += AIB::query(m - yv - 1);
            }
            while(p)
                AIB::update(m - LinH[i][j][--p].second - 1, -1);
        }
    }
	return re;
}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:162:46: warning: unused variable 'l2' [-Wunused-variable]
  162 |             int l1 = (int)LinH[i][j].size(), l2 = (int)LinV[i][j].size();
      |                                              ^~
rect.cpp:145:10: warning: variable 'inclus' set but not used [-Wunused-but-set-variable]
  145 |     auto inclus = [&](ii a, ii b) {
      |          ^~~~~~
rect.cpp: In function 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > get_linii(std::vector<std::vector<int> >&)':
rect.cpp:87:57: warning: array subscript -1 is below array bounds of 'std::vector<std::pair<int, int> > [2500][2500]' [-Warray-bounds]
   87 |                     for(auto [s1, d1]: Perechi[p - 1][st])
      |                                        ~~~~~~~~~~~~~~~~~^
rect.cpp:40:12: note: while referencing 'Perechi'
   40 | vector<ii> Perechi[MN][MN];
      |            ^~~~~~~
rect.cpp:89:57: warning: array subscript -1 is below array bounds of 'std::vector<std::pair<int, int> > [2500][2500]' [-Warray-bounds]
   89 |                     for(auto [s1, d1]: Perechi[p - 1][dr])
      |                                        ~~~~~~~~~~~~~~~~~^
rect.cpp:40:12: note: while referencing 'Perechi'
   40 | vector<ii> Perechi[MN][MN];
      |            ^~~~~~~

• 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