Submission #889396

#	Time	Username	Problem	Language	Result	Execution time	Memory
889396		vjudge1	Rectangles (IOI19_rect)	C++17	0 / 100	3 ms	2140 KiB

rect

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


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 = -1;
            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)
                        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)
                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[2];
        ++it[3];
    }

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

    int re = 0;

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

	return re;
}

• 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