Submission #1069506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069506		becaido	Rectangles (IOI19_rect)	C++17	100 / 100	4208 ms	930440 KiB

rect

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "rect.h"
#else
#include "grader.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2505;

int n, m;
ll ans;
int a[SIZE][SIZE];
int U[SIZE], D[SIZE], L[SIZE], R[SIZE];
vector<tuple<int, int, int>> xseg, yseg;
vector<pair<int, int>> xop[SIZE][SIZE], yop[SIZE][SIZE];

int bit[SIZE];
void upd(int pos, int x) {
    for (; pos <= m; pos += pos & -pos) bit[pos] += x;
}
int que(int pos) {
    int re = 0;
    for (; pos; pos -= pos & -pos) re += bit[pos];
    return re;
}

ll count_rectangles(vector<vector<int>> _a) {
    n = _a.size(), m = _a[0].size(), ans = 0;
    fill(bit + 1, bit + m + 1, 0);
    xseg.clear(), yseg.clear();
    FOR (i, 1, n) FOR (j, 1, m) {
        a[i][j] = _a[i - 1][j - 1];
        xop[i][j].clear();
        yop[i][j].clear();
    }

    FOR (i, 1, n) {
        vector<pair<int, int>> seg;
        vector<int> st;
        FOR (j, 1, m) {
            while (st.size() && a[i][j] >= a[i][st.back()]) st.pop_back();
            L[j] = (st.size() ? st.back() : 0);
            st.pb(j);
        }
        st.clear();
        for (int j = m; j >= 1; j--) {
            while (st.size() && a[i][j] >= a[i][st.back()]) st.pop_back();
            R[j] = (st.size() ? st.back() : m + 1);
            st.pb(j);
        }
        FOR (j, 1, m) if (1 <= L[j] && R[j] <= m) seg.pb(L[j] + 1, R[j] - 1);
        sort(seg.begin(), seg.end());
        seg.erase(unique(seg.begin(), seg.end()), seg.end());
        for (auto [l, r] : seg) xseg.pb(l, r, i);
    }

    FOR (j, 1, m) {
        vector<pair<int, int>> seg;
        vector<int> st;
        FOR (i, 1, n) {
            while (st.size() && a[i][j] >= a[st.back()][j]) st.pop_back();
            U[i] = (st.size() ? st.back() : 0);
            st.pb(i);
        }
        st.clear();
        for (int i = n; i >= 1; i--) {
            while (st.size() && a[i][j] >= a[st.back()][j]) st.pop_back();
            D[i] = (st.size() ? st.back() : n + 1);
            st.pb(i);
        }
        FOR (i, 1, n) if (1 <= U[i] && D[i] <= n) seg.pb(U[i] + 1, D[i] - 1);
        sort(seg.begin(), seg.end());
        seg.erase(unique(seg.begin(), seg.end()), seg.end());
        for (auto [u, d] : seg) yseg.pb(u, d, j);
    }

    sort(xseg.begin(), xseg.end());
    sort(yseg.begin(), yseg.end());
    for (int il = 0, ir; il < xseg.size(); il = ir + 1) {
        ir = il;
        while (ir < xseg.size() && get<0>(xseg[il]) == get<0>(xseg[ir + 1]) && get<1>(xseg[il]) == get<1>(xseg[ir + 1]) && get<2>(xseg[ir]) + 1 == get<2>(xseg[ir + 1])) ir++;
        auto [l, r, u] = xseg[il];
        int d = get<2>(xseg[ir]);
        FOR (i, u, d) xop[i][l].pb(r, d);
    }
    for (int il = 0, ir; il < yseg.size(); il = ir + 1) {
        ir = il;
        while (ir < yseg.size() && get<0>(yseg[il]) == get<0>(yseg[ir + 1]) && get<1>(yseg[il]) == get<1>(yseg[ir + 1]) && get<2>(yseg[ir]) + 1 == get<2>(yseg[ir + 1])) ir++;
        auto [u, d, l] = yseg[il];
        int r = get<2>(yseg[ir]);
        FOR (j, l, r) yop[u][j].pb(d, r);
    }

    FOR (u, 1, n) FOR (l, 1, m) if (xop[u][l].size() && yop[u][l].size()) {
        vector<tuple<int, int, int>> op;
        for (auto [r, d] : xop[u][l]) {
            op.pb(u, r, 1);
            op.pb(d + 1, r, -1);
        }
        for (auto [d, r] : yop[u][l]) op.pb(d, r, 0);
        sort(op.begin(), op.end(), [&](auto x, auto y) {
            return get<0>(x) != get<0>(y) ? get<0>(x) < get<0>(y) : abs(get<2>(x)) > abs(get<2>(y));
        });
        for (auto [d, r, t] : op) {
            if (t) upd(r, t);
            else ans += que(r);
        }
    }
    return ans;
}

/*
in1
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
out1
6
*/

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:99:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int il = 0, ir; il < xseg.size(); il = ir + 1) {
      |                          ~~~^~~~~~~~~~~~~
rect.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         while (ir < xseg.size() && get<0>(xseg[il]) == get<0>(xseg[ir + 1]) && get<1>(xseg[il]) == get<1>(xseg[ir + 1]) && get<2>(xseg[ir]) + 1 == get<2>(xseg[ir + 1])) ir++;
      |                ~~~^~~~~~~~~~~~~
rect.cpp:106:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int il = 0, ir; il < yseg.size(); il = ir + 1) {
      |                          ~~~^~~~~~~~~~~~~
rect.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         while (ir < yseg.size() && get<0>(yseg[il]) == get<0>(yseg[ir + 1]) && get<1>(yseg[il]) == get<1>(yseg[ir + 1]) && get<2>(yseg[ir]) + 1 == get<2>(yseg[ir + 1])) ir++;
      |                ~~~^~~~~~~~~~~~~

• 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