Submission #889448

#	Time	Username	Problem	Language	Result	Execution time	Memory
889448		vjudge1	Rectangles (IOI19_rect)	C++17	37 / 100	5082 ms	77900 KiB

rect

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

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")


using namespace std;

using vi = vector<int>;
using i4 = array<int, 4>;
using vi4 = vector<i4>;

void extract(int n, int m, vector<vi> &V, vi4 &V1) {
    vector<stack<int> > lin(m);
    for(int j = 0; j < m; ++j)
        lin[j].push(0);
    set<int> Cur;
    for(int i = 1; i < n; ++i) {
        vector<pair<int, int> > Ult, UrmU; /// perechi (linie, j din trecut)
        for(int j = 0; j < m; ++j) {
            Cur.clear();
            int uv = V[i][j];
            while(!lin[j].empty() && V[i][j] > V[lin[j].top()][j]) {
                if(V[lin[j].top()][j] != uv) {
                    Cur.insert(lin[j].top());
                    uv = V[lin[j].top()][j];
                }
                lin[j].pop();
            }
            if(!lin[j].empty()) {
                if(V[lin[j].top()][j] != uv) { // desc
                    Cur.insert(lin[j].top());
                    uv = V[lin[j].top()][j];
                }
            }
            lin[j].push(i);
            UrmU.clear();
            for(auto [l, jv] : Ult) {
                if(Cur.count(l)) {
                    UrmU.push_back({l, jv});
                    Cur.erase(l);
                } else {
                    if(abs(l - i) > 1 && j - 1 - jv >= 0)
                        V1.push_back(i4{l, i, jv, j - 1});
                }
            }
            swap(Ult, UrmU);
            for(auto vc : Cur)
                Ult.push_back({vc, j});
        }
        for(auto [l, jv] : Ult) {
            if(abs(l - i) > 1 && m - 1 - jv >= 0)
                V1.push_back(i4{l, i, jv, m - 1});
        }
    }
}

long long count_rectangles(std::vector<std::vector<int> > V) {
    int n = V.size(), m = V[0].size();
    vector<vi> VT(m, vi(n, 0));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j) 
            VT[j][i] = V[i][j];

    vi4 V1, V2;

    extract(n, m, V, V1);
    extract(m, n, VT, V2);
    for(auto &it : V2) {
        swap(it[0], it[2]);
        swap(it[1], it[3]);
    }

    for(auto &it : V1) {
        ++it[0];
        --it[1];
    }

    for(auto &it : V2) {
        ++it[2];
        --it[3];
    }

    int re = 0, re2 = 0;

    for(auto &it : V1) {
        it[0] *= -1;
        it[3] *= -1;
    }
    for(auto &it : V2) {
        it[0] *= -1;
        it[3] *= -1;
    }

    for(auto it1 : V1) {
        for(auto it2 : V2) {
            int ok = 1;
            for(int i = 0; i < 4; ++i) {
                if(it2[i] >= it1[i]);
                else ok = 0;
            }
            re += ok;
        }
    }

	return re;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:86:17: warning: unused variable 're2' [-Wunused-variable]
   86 |     int re = 0, re2 = 0;
      |                 ^~~

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