Submission #889447

#	Time	Username	Problem	Language	Result	Execution time	Memory
889447		vjudge1	Rectangles (IOI19_rect)	C++17	37 / 100	5048 ms	85004 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 = 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];
    }
//    cout << "\n";
//
//    for(auto it : V1) {
//        for(int i = 0; i < 4; ++i)
//            cout << it[i] << " ";
//        cout << "\n";
//    }
//    cout << "\n";
//    for(auto it : V2) {
//        for(int i = 0; i < 4; ++i)
//            cout << it[i] << " ";
//        cout << "\n";
//    }
//    cout << "\n";

    int re = 0, re2 = 0;

    for(auto it1 : V1) {
 //       if(it1[1] - it1[0] <= 1 || it1[3] - it1[2] <= 1) continue;
        for(auto it2 : V2) {
//            if(it2[1] - it2[0] <= 1 || it2[3] - it2[2] <= 1) continue;
            int ok = 1;
            int ok2 = 1;
            for(int i = 0; i < 4; ++i) {
                int sgn = 1;
                if(i == 0 || i == 3) sgn = -1;
                if(it2[i] * sgn >= it1[i] * sgn)  {
                    if(it2[i] != it1[i]) ok2 = 0;
                }
                else ok = 0;
            }
            re2 += ok2;
            re += ok;
        }
    }
//    cout << "Cealalta var : " << re2 << "\n";

	return re;
}

• 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