Submission #310065

#	Time	Username	Problem	Language	Result	Execution time	Memory
310065		fivefourthreeone	Rectangles (IOI19_rect)	C++17	Compilation error	0 ms	0 KiB

rect

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const int mxN = 2501;
int n, m;
int BIT[mxN][mxN];
vector<vector<int>> arr;
vector<int> atrow[mxN][mxN];
vector<pair<int, int>> atcol[mxN];
vector<int> len[mxN];
vector<int> ch[mxN];
void upd(int num, int pos, int del) {
    pos++;
    while(pos < n) {
        BIT[num][pos]+=del;
        pos += pos&-pos;
    }
}
int sum(int num, int pos, int del) {
    pos++;
    while(pos) {
        BIT[num][pos]+=del;
        pos -= pos&-pos;
    }
}
ll count_rectangles(vector<vector<int>> A) {
    arr = A;
    n = A.size();
    m = A[0].size();
    for(int i = 1; i < n-1; ++i) {
        vector<int> stk;
        for(int j = 0; j < m; ++j) {
            while(stk.size() && arr[i][stk.back()] < arr[i][j])stk.pop_back();
            if(stk.size() && j - stk.back() > 1) {
                atcol[i].emplace_back(stk.back(), j);
            }
            stk.push_back(j);
        }
        stk.clear();
        for(int j = m-1; j >= 0; --j) {
            while(stk.size() && arr[i][stk.back()] < arr[i][j])stk.pop_back();
            if(stk.size() && stk.back() - j > 1) {
                atcol[i].emplace_back(j, stk.back());
            }
            stk.push_back(j);
        }
        sort(atcol[i].begin(), atcol[i].end());
        atcol[i].resize(unique(atcol[i].begin(), atcol[i].end()) - atcol[i].begin());
    }
    for(int j = 1; j < m-1; ++j) {
        vector<int> stk;
        vector<pair<int, int>> ex;
        for(int i = 0; i < n; ++i) {
            while(stk.size() && arr[stk.back()][j] < arr[i][j])stk.pop_back();
            if(stk.size() && i - stk.back() > 1) {
                ex.emplace_back(stk.back(), i);
            }
            stk.push_back(i);
        }
        stk.clear();
        for(int i = n-1; i >= 0; --i) {
            while(stk.size() && arr[stk.back()][j] < arr[i][j])stk.pop_back();
            if(stk.size() && stk.back() - i > 1) {
                ex.emplace_back(i, stk.back());
            }
            stk.push_back(i);
        }
        sort(ex.begin(), ex.end());
        ex.resize(unique(ex.begin(), ex.end()) - ex.begin());
        for(auto p: ex) {
            atrow[p.first][p.second].push_back(j);
        }
    }
    for(int j = m-1; j > 1; --j) {
        len[j].resize(atcol[j].size());
        for(int i = 0; i < atcol[j].size(); ++i) {
            int above = lower_bound(atcol[j+1].begin(), atcol[j+1].end(), atcol[j][i]) - atcol[j+1].begin();
            if(above==atcol[j+1].size() || atcol[j+1][above]!=atcol[j][i]) {
                len[j][i] = 1;
            }else {
                len[j][i] = len[j+1][above] + 1;
            }
        }
    }
    ll res = 0;
    for(int i = 1; j < m-1; ++i) {
        for(int j = i; j < m-1; ++j) {
            ch[j].clear();
        }
        for(int j = 0; j < atcol[i].size(); ++j) {
            upd(atcol[i][j].first, atcol[i][j].second, 1);
            ch[i + len[i][j] - 1].push_back(j);
        }
        for(int j = i; j < m-1; ++j) {
            int prv = 1;
            for(int k = 0; k < atrow[i+1][j-1].size(); ++k) {
                if(k && atrow[i+1][j-1][k-1]==atrow[i+1][j-1][k]-1)prv++;
                else prv = 1;
                res += sum(atrow[i+1][j-1][k] - prv, atrow[i+1][j-1][k] + 1);
            }
            for(int k: ch[j]) {
                upd(atcol[i][k].first, atcol[i][k].second, -1);
            }
        }
    }
    return res;
}

Compilation message (stderr)

rect.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
rect.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
rect.cpp: In function 'int sum(int, int, int)':
rect.cpp:29:1: warning: no return statement in function returning non-void [-Wreturn-type]
   29 | }
      | ^
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:80:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int i = 0; i < atcol[j].size(); ++i) {
      |                        ~~^~~~~~~~~~~~~~~~~
rect.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             if(above==atcol[j+1].size() || atcol[j+1][above]!=atcol[j][i]) {
      |                ~~~~~^~~~~~~~~~~~~~~~~~~
rect.cpp:90:20: error: 'j' was not declared in this scope
   90 |     for(int i = 1; j < m-1; ++i) {
      |                    ^
rect.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int j = 0; j < atcol[i].size(); ++j) {
      |                        ~~^~~~~~~~~~~~~~~~~
rect.cpp:100:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for(int k = 0; k < atrow[i+1][j-1].size(); ++k) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:103:76: error: too few arguments to function 'int sum(int, int, int)'
  103 |                 res += sum(atrow[i+1][j-1][k] - prv, atrow[i+1][j-1][k] + 1);
      |                                                                            ^
rect.cpp:23:5: note: declared here
   23 | int sum(int num, int pos, int del) {
      |     ^~~