Submission #969295

#	Time	Username	Problem	Language	Result	Execution time	Memory
969295		NemanjaSo2005	Rectangles (IOI19_rect)	C++17	10 / 100	762 ms	280216 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int MAXN = 2505;
ll res = 0;
int N, M;
int L[MAXN], R[MAXN];
stack<int> S;
map<pair<int,int>,int> mapa[MAXN];
vector<pair<int,int>> getinterval(vector<int> &V){
    vector<pair<int,int>> res;
    while (!S.empty())
        S.pop();
    S.push(0);
    L[0] = -1;
    for (int i = 1; i < V.size(); i++) {
        while (!S.empty() && V[S.top()] <= V[i])
            S.pop();
        if (S.empty())
            L[i] = -1;
        else
            L[i] = S.top() + 1;
        S.push(i);
    }

    while (!S.empty())
        S.pop();

    S.push(V.size() - 1);
    for (int i = V.size() - 2; i >= 1; i--) {
        while (!S.empty() && V[S.top()] <= V[i])
            S.pop();
        if (S.empty())
            R[i] = -1;
        else
            R[i] = S.top() - 1;
        S.push(i);
    }

    for (int i = 1; i < V.size() - 1; i++) {
        if (L[i] == -1 || R[i] == -1)
            continue;
        res.push_back({L[i], R[i]});
    }

    if (res.size()) {
        sort(res.begin(), res.end());
        vector<pair<int,int>> r2;
        r2.push_back(res[0]);
        for (int i = 1; i < res.size(); i++)
            if (res[i] != res[i - 1])
                r2.push_back(res[i]);
        return r2;
    }
    return res;
}

struct slog {
    int duz, kol;
};

bool poduz(slog a, slog b) {
    return a.duz < b.duz;
}

bool pokol(slog a, slog b) {
    return a.kol < b.kol;
}

vector<slog> vert[MAXN][MAXN];
int fwt[MAXN];

void add(int x, int kol) {
    x++;
    for (int i = x; i <= MAXN; i += i & -i)
        fwt[i] += kol;
}

int sum(int x) {
    int r = 0;
    x++;
    for (int i = x; i >= 1; i -= i & -i)
        r += fwt[i];
    return r;
}

ll resi(vector<slog> &A, vector<slog> &B) {
    ll ret = 0;
    sort(A.begin(), A.end(), poduz);
    sort(B.begin(), B.end(), pokol);

    for (int i = 0; i < B.size(); i++)
        add(B[i].duz, 1);
    int pok = 0;

    for (int i = 0; i < A.size(); i++) {
        while (pok < B.size() && B[pok].kol < A[i].duz) {
            add(B[pok].duz, -1);
            pok++;
        }
        ret += sum(A[i].kol);
    }

    while (pok < B.size()) {
        add(B[pok].duz, -1);
        pok++;
    }

    return ret;
}

ll count_rectangles(vector<vector<int>> inp) {
    N = inp.size();
    M = inp[0].size();

    for (int i = N - 2; i >= 1; i--) {
        vector<int> V;
        for (int j = 0; j < M; j++)
            V.push_back(inp[i][j]);
        auto I = getinterval(V);
        for (auto x : I) {
            if (mapa[i + 1].find(x) != mapa[i + 1].end())
                mapa[i][x] = mapa[i + 1][x] + 1;
            else
                mapa[i][x] = 1;

            slog pp;
            pp.kol = mapa[i][x];
            pp.duz = x.second - x.first + 1;
            vert[i][x.first].push_back(pp);
        }
    }

    ll res = 0;
    for (int i = M - 2; i >= 1; i--) {
        vector<int> V;
        for (int j = 0; j < N; j++)
            V.push_back(inp[j][i]);
        auto I = getinterval(V);
        if (I.size() == 0)
            continue;
        vector<slog> PV;
        int px = I[0].first;
        for (auto x : I) {
            if (x.first != px) {
                res += resi(vert[px][i], PV);
                px = x.first;
                PV.clear();
            }

            if (mapa[i + 1].find(x) != mapa[i + 1].end())
                mapa[i][x] = mapa[i + 1][x] + 1;
            else
                mapa[i][x] = 1;

            slog pp;
            pp.kol = mapa[i][x];
            pp.duz = x.second - x.first + 1;
            PV.push_back(pp);
        }
        res += resi(vert[px][i], PV);
    }

    return res;
}

Compilation message (stderr)

rect.cpp: In function 'std::vector<std::pair<int, int> > getinterval(std::vector<int>&)':
rect.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 1; i < V.size(); i++) {
      |                     ~~^~~~~~~~~~
rect.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 1; i < V.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~
rect.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int i = 1; i < res.size(); i++)
      |                         ~~^~~~~~~~~~~~
rect.cpp: In function 'long long int resi(std::vector<slog>&, std::vector<slog>&)':
rect.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i = 0; i < B.size(); i++)
      |                     ~~^~~~~~~~~~
rect.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i = 0; i < A.size(); i++) {
      |                     ~~^~~~~~~~~~
rect.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         while (pok < B.size() && B[pok].kol < A[i].duz) {
      |                ~~~~^~~~~~~~~~
rect.cpp:107:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     while (pok < B.size()) {
      |            ~~~~^~~~~~~~~~

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