Submission #154565

#	Time	Username	Problem	Language	Result	Execution time	Memory
154565		crackersamdjam	Rectangles (IOI19_rect)	C++14	72 / 100	5107 ms	1024288 KiB

rect

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4,popcnt,abm,mmx,tune=native")

#include <bits/stdc++.h>

#define INT_INF 0x3f3f3f3f
#define mp std::make_pair

#define MAXN 2501

typedef long long ll;
typedef std::pair<int,int> pii;

int num_rows,num_cols,arr[MAXN][MAXN],bit[MAXN],cnt[MAXN][MAXN],ans,l,r,lst[MAXN],pp;
std::vector<pii> row_dp[MAXN][MAXN],col_dp[MAXN][MAXN];
std::vector<std::pair<pii,int>> dep[MAXN];
pii dq[MAXN];

inline void update(int i, int val, int curr){
    for(; i<=num_cols; i+=i&-i){
        if(lst[i] != curr) bit[i] = val, lst[i] = curr;
        else bit[i]+=val;
    }
}

inline int query(int i, int curr){
    static int res;
    res = 0;
    for(; i>0; i-=i&-i)
        if(lst[i] == curr)
            res+=bit[i];
    return res;
}

inline void init_rows(){
//	memset(cnt,0,sizeof cnt);
    for(int i=2; i<num_rows; i++){
        l = 1, r = 0;
        for(int k=1; k<=num_cols; k++){
            while(r-l+1 > 0 && dq[r].first < arr[i][k]) r--;
            int lft = (r-l+1>0?dq[r].second:INT_INF);
            if(lft < k-1 && (row_dp[lft+1][k-1].empty() || row_dp[lft+1][k-1].back().first != i))
                row_dp[lft+1][k-1].emplace_back(i,i), cnt[lft+1][k-1]++; //rows[i].pb(mp(lft+1,k-1));
            while(r-l+1 > 0 && dq[r].first == arr[i][k]) r--;
            dq[++r] = mp(arr[i][k],k);
        }
        l = 1, r = 0;
        for(int k=num_cols; k>=1; k--){
            while(r-l+1 > 0 && dq[r].first < arr[i][k]) r--;
            int rgt = (r-l+1>0?dq[r].second:-INT_INF);
            if(rgt > k+1 && (row_dp[k+1][rgt-1].empty() || row_dp[k+1][rgt-1].back().first != i))
                row_dp[k+1][rgt-1].emplace_back(i,i), cnt[k+1][rgt-1]++; //rows[i].pb(mp(k+1,rgt-1));
            while(r-l+1 > 0 && dq[r].first == arr[i][k]) r--;
            dq[++r] = mp(arr[i][k],k);
        }
    }
}

inline void init_cols(){
    memset(cnt,0,sizeof cnt);
    for(int i=2; i<num_cols; i++){
        l = 1, r = 0;
        for(int k=1; k<=num_rows; k++){
            while(r-l+1 > 0 && dq[r].first < arr[k][i]) r--;
            int lft = (r-l+1>0?dq[r].second:INT_INF);
            if(lft < k-1 && (col_dp[lft+1][k-1].empty() || col_dp[lft+1][k-1].back().first != i))
                col_dp[lft+1][k-1].emplace_back(i,i), cnt[lft+1][k-1]++; //cols[i].pb(mp(lft+1,k-1));
            while(r-l+1 > 0 && dq[r].first == arr[k][i]) r--;
            dq[++r] = mp(arr[k][i],k);
        }
        l = 1, r = 0;
        for(int k=num_rows; k>=1; k--){
            while(r-l+1 > 0 && dq[r].first < arr[k][i]) r--;
            int rgt = (r-l+1>0?dq[r].second:-INT_INF);
            if(rgt > k+1 && (col_dp[k+1][rgt-1].empty() || col_dp[k+1][rgt-1].back().first != i))
                col_dp[k+1][rgt-1].emplace_back(i,i), cnt[k+1][rgt-1]++; //cols[i].pb(mp(k+1,rgt-1));
            while(r-l+1 > 0 && dq[r].first == arr[k][i]) r--;
            dq[++r] = mp(arr[k][i],k);
        }
    }
}

#define nums row_dp[l][r]
inline void calc_hor_dp(){
    for(int l=2; l<=num_cols-1; l++){
        for(int r=l; r<=num_cols-1; r++){
            if(cnt[l][r] == 0) continue;
            int lst = 0;
            for(int i=1; i<cnt[l][r]; i++){
                if(nums[i].first == nums[i-1].first+1) continue;
                for(int k=nums[lst].first; k<=nums[i-1].first; k++)
                    dep[nums[i-1].first-k+1].emplace_back(mp(k,l),r);
                lst = i;
            }
            for(int k=nums[lst].first; k<=nums[cnt[l][r]-1].first; k++)
                dep[nums[cnt[l][r]-1].first-k+1].emplace_back(mp(k,l),r);
            nums.clear();
        }
    }
    for(int i=1; i<=num_rows; i++){
        for(auto &check:dep[i])
            row_dp[check.first.first][check.first.second].emplace_back(i,check.second);
    }
}

#define nums col_dp[l][r]

inline void calc_col_dp(){
    for(int l=2; l<=num_rows-1; l++){
        for(int r=l; r<=num_rows-1; r++){
            if(cnt[l][r] == 0) continue;
            int lst = 0;
            for(int i=1; i<cnt[l][r]; i++){
                if(nums[i].first == nums[i-1].first+1) continue;
                for(int k=nums[lst].first; k<=nums[i-1].first; k++)
                    col_dp[l][k].emplace_back(r,nums[i-1].first);
                lst = i;
            }
            for(int k=nums[lst].first; k<=nums[cnt[l][r]-1].first; k++)
                col_dp[l][k].emplace_back(r,nums[cnt[l][r]-1].first);
        }
    }
}

ll count_rectangles(std::vector<std::vector<int>> a){
    num_rows = a.size(), num_cols = a[0].size();
    for(int i=0; i<a.size(); i++)
        for(int k=0; k<a[i].size(); k++)
            arr[i+1][k+1] = a[i][k];
    init_rows(); calc_hor_dp();
    init_cols(); calc_col_dp();
    for(int i=num_rows-1; i>=2; i--){
        for(int k=num_cols-1; k>=2; k--){
            int ptr = cnt[i][k], res = 0, cc = 0; ++pp;
            for(int v=0; v<row_dp[i][k].size(); v++){
                while(ptr < col_dp[i][k].size() && col_dp[i][k][ptr].first-i+1 <= row_dp[i][k][v].first){
                    update(col_dp[i][k][ptr].second-k+1,1,pp);
                    ptr++, cc++;
                }
                res+=cc-query(row_dp[i][k][v].second-k,pp);
            }
            ans+=res;
        }
    }
    return ans;
}

Compilation message (stderr)

rect.cpp:107:0: warning: "nums" redefined
 #define nums col_dp[l][r]
 
rect.cpp:84:0: note: this is the location of the previous definition
 #define nums row_dp[l][r]
 
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:128:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++)
                  ~^~~~~~~~~
rect.cpp:129:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int k=0; k<a[i].size(); k++)
                      ~^~~~~~~~~~~~
rect.cpp:136:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int v=0; v<row_dp[i][k].size(); v++){
                          ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:137:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(ptr < col_dp[i][k].size() && col_dp[i][k][ptr].first-i+1 <= row_dp[i][k][v].first){
                       ~~~~^~~~~~~~~~~~~~~~~~~~~

• 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: 0 / 28