Submission #310113

#	Time	Username	Problem	Language	Result	Execution time	Memory
310113		fivefourthreeone	Rectangles (IOI19_rect)	C++17	23 / 100	1301 ms	312696 KiB

rect

#include "rect.h"
#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 res = 0;
    pos++;
    while(pos) {
        res+=BIT[num][pos];
        pos -= pos&-pos;
    }
    return res;
}
ll count_rectangles(vector<vector<int>> A) {
    arr = A;
    n = A.size();
    m = A[0].size();
    for(int i = 1; i < m-1; ++i) {
        vector<int> stk;
        for(int j = 0; j < n; ++j) {
            while(stk.size() && arr[stk.back()][i] < arr[j][i])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 = n-1; j >= 0; --j) {
            while(stk.size() && arr[stk.back()][i] < arr[j][i])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 i = 1; i < n-1; ++i) {
        vector<int> stk;
        vector<pair<int, int>> ex;
        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) {
                ex.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) {
                ex.emplace_back(j, stk.back());
            }
            stk.push_back(j);
        }
        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(i);
        }
    }
    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; i < 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;
                //cout<<sum(atrow[i-1][j+1][k] - prv, atrow[i-1][j+1][k]+1)<<"\n";
                int val = sum(atrow[i-1][j+1][k] - prv, atrow[i-1][j+1][k] + 1);
                res += val;
            }
            for(int k: ch[j]) {
                upd(atcol[i][k].first, atcol[i][k].second, -1);
            }
        }
    }
    return res;
}
/*int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin>>n>>m;
    vector<vector<int>> arr;
    arr.resize(n);
    for(int i = 0; i < n; ++i){
        arr[i].resize(m);
        for(int j = 0; j < m; ++j) {
            cin>>arr[i][j];
        }
    }
    cout<<count_rectangles(arr)<<"\n";
    return 0;
}*/

Compilation message (stderr)

rect.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
rect.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:83: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]
   83 |         for(int i = 0; i < atcol[j].size(); ++i) {
      |                        ~~^~~~~~~~~~~~~~~~~
rect.cpp:85: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]
   85 |             if(above==atcol[j+1].size() || atcol[j+1][above]!=atcol[j][i]) {
      |                ~~~~~^~~~~~~~~~~~~~~~~~~
rect.cpp:97: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]
   97 |         for(int j = 0; j < atcol[i].size(); ++j) {
      |                        ~~^~~~~~~~~~~~~~~~~
rect.cpp:103:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             for(int k = 0; k < atrow[i-1][j+1].size(); ++k) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~

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