Submission #290372

#	Time	Username	Problem	Language	Result	Execution time	Memory
290372		evpipis	Rectangles (IOI19_rect)	C++17	100 / 100	3604 ms	275960 KiB

rect

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ii, int> inter;

const int len = 2505, mx = 2500;
int mat[len][len], po[len], n, m;
int bit[len][len];
vector<inter> row[len], col[len];

void upd(int i, int j, int v){
    while (j <= mx)
        bit[i][j] += v, j += j&(-j);
}

int ask(int i, int j){
    int ans = 0;
    while (j > 0)
        ans += bit[i][j], j -= j&(-j);
    return ans;
}

vector<inter> make_inter(vector<int> vec){
    vector<inter> res;

    vector<int> stck;
    for (int i = 0; i < vec.size(); i++){
        while (!stck.empty() && vec[i] > vec[stck.back()])
            stck.pop_back();

        if (!stck.empty() && stck.back() < i-1)
            res.pb(mp(mp(stck.back()+1, i-1), 1));

        stck.pb(i);
    }

    stck.clear();
    for (int i = (int)vec.size()-1; i >= 0; i--){
        while (!stck.empty() && vec[i] > vec[stck.back()])
            stck.pop_back();

        if (!stck.empty() && stck.back() > i+1)
            res.pb(mp(mp(i+1, stck.back()-1), 1));

        stck.pb(i);
    }

    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    return res;
}

bool comp1(inter a, inter b){
    return (a.se > b.se);
}

bool comp2(inter a, inter b){
    return (a.fi.se-a.fi.fi > b.fi.se-b.fi.fi);
}

ll count_rectangles(vector<vector<int> > M) {
    n = M.size(), m = M[0].size();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            mat[i][j] = M[i][j];

    for (int i = n-1; i >= 0; i--){
        vector<int> vec;
        for (int j = 0; j < m; j++)
            vec.pb(mat[i][j]);
        row[i] = make_inter(vec);

        for (int k = 0, l = 0; k < row[i].size(); k++){
            while (l < row[i+1].size() && row[i+1][l].fi < row[i][k].fi)
                l++;

            if (l < row[i+1].size() && row[i+1][l].fi == row[i][k].fi)
                row[i][k].se += row[i+1][l].se;
        }

        /*printf("row#%d\n", i);
        for (auto cur: row[i])
            printf("[(%d, %d), %d] ", cur.fi.fi, cur.fi.se, cur.se);
        printf("\n");*/
    }

    for (int j = m-1; j >= 0; j--){
        vector<int> vec;
        for (int i = 0; i < n; i++)
            vec.pb(mat[i][j]);
        col[j] = make_inter(vec);

        for (int k = 0, l = 0; k < col[j].size(); k++){
            while (l < col[j+1].size() && col[j+1][l].fi < col[j][k].fi)
                l++;

            if (l < col[j+1].size() && col[j+1][l].fi == col[j][k].fi)
                col[j][k].se += col[j+1][l].se;
        }

        /*printf("col#%d\n", j);
        for (auto cur: col[j])
            printf("[(%d, %d), %d] ", cur.fi.fi, cur.fi.se, cur.se);
        printf("\n");*/
    }

    ll ans = 0;
    for (int j = 0; j < m; j++)
        po[j] = 0;
    for (int row1 = 0; row1 < n; row1++){
        vector<inter> vec;
        for (int j = 0; j < m; j++)
            while (po[j] < col[j].size() && col[j][po[j]].fi.fi == row1)
                vec.pb(mp(mp(j, col[j][po[j]].fi.se), col[j][po[j]].se)), po[j]++;
        sort(vec.begin(), vec.end(), comp1);

        sort(row[row1].begin(), row[row1].end(), comp2);

        //printf("after sort: row1 = %d\n", row1);

        int j = 0;
        for (int i = 0; i < row[row1].size(); i++){
            int col1 = row[row1][i].fi.fi, col2 = row[row1][i].fi.se;
            int row2 = row1+row[row1][i].se-1;

            while (j < vec.size() && vec[j].se >= col2-col1+1)
                upd(vec[j].fi.fi, vec[j].fi.se, +1), j++;

            ans += ask(col1, row2);
        }

        while (j > 0){
            j--;
            upd(vec[j].fi.fi, vec[j].fi.se, -1);
        }
    }

	return ans;
}

/*
10 10
3 2 2 2 5 1 1 1 1 1
3 1 1 1 2 1 1 1 1 1
6 2 2 2 3 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
*/

Compilation message (stderr)

rect.cpp: In function 'std::vector<std::pair<std::pair<int, int>, int> > make_inter(std::vector<int>)':
rect.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < vec.size(); i++){
      |                     ~~^~~~~~~~~~~~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:81:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int k = 0, l = 0; k < row[i].size(); k++){
      |                                ~~^~~~~~~~~~~~~~~
rect.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             while (l < row[i+1].size() && row[i+1][l].fi < row[i][k].fi)
      |                    ~~^~~~~~~~~~~~~~~~~
rect.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             if (l < row[i+1].size() && row[i+1][l].fi == row[i][k].fi)
      |                 ~~^~~~~~~~~~~~~~~~~
rect.cpp:101:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for (int k = 0, l = 0; k < col[j].size(); k++){
      |                                ~~^~~~~~~~~~~~~~~
rect.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |             while (l < col[j+1].size() && col[j+1][l].fi < col[j][k].fi)
      |                    ~~^~~~~~~~~~~~~~~~~
rect.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             if (l < col[j+1].size() && col[j+1][l].fi == col[j][k].fi)
      |                 ~~^~~~~~~~~~~~~~~~~
rect.cpp:121:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             while (po[j] < col[j].size() && col[j][po[j]].fi.fi == row1)
      |                    ~~~~~~^~~~~~~~~~~~~~~
rect.cpp:130:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for (int i = 0; i < row[row1].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~
rect.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             while (j < vec.size() && vec[j].se >= col2-col1+1)
      |                    ~~^~~~~~~~~~~~

• 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