Submission #597144

#	Time	Username	Problem	Language	Result	Execution time	Memory
597144		alirezasamimi100	Rectangles (IOI19_rect)	C++17	100 / 100	2360 ms	738928 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define mp make_pair
using pii = pair<int,int>;
using ll = long long int;

const int N = 2.5e3 + 10;

int ans,n,m,f[N];
vector<pii> R[N][N],C[N][N];
void upd(int t, int x){
    for(t+=5; t<N; t+=t&-t) f[t]+=x;
}
int get(int t, int x=0){
    for(t+=5; t; t-=t&-t) x+=f[t];
    return x;
}

ll count_rectangles(vector<vector<int> > A) {
    n=A.size();
    m=A[0].size();
    for(int i=0; i<n; i++){
        vector<int> st;
        for(int j=0; j<m; j++){
            int f=0;
            while(!st.empty() && A[i][st.back()]<=A[i][j]){
                if(A[i][st.back()]==A[i][j]) f=1;
                if(j-st.back()>1){
                    R[i][st.back()+1].pb({j-1,i});
                }
                st.pop_back();
            }
            if(!f && !st.empty() && j-st.back()>1) R[i][st.back()+1].pb({j-1,i});
            st.pb(j);
        }
    }
    for(int j=0; j<m; j++){
        vector<int> st;
        for(int i=0; i<n; i++){
            int f=0;
            while(!st.empty() && A[st.back()][j]<=A[i][j]){
                if(A[st.back()][j]==A[i][j]) f=1;
                if(i-st.back()>1){
                    C[st.back()+1][j].pb({i-1,j});
                }
                st.pop_back();
            }
            if(!f && !st.empty() && i-st.back()>1) C[st.back()+1][j].pb({i-1,j});
            st.pb(i);
        }
    }
    for(int i=n-1; i--; ){
        for(int j=m-1; j--; ){
            for(int k=0; k<(int)R[i][j].size(); k++){
                auto it=lower_bound(R[i+1][j].begin(),R[i+1][j].end(),mp(R[i][j][k].F,-1));
                if(it!=R[i+1][j].end() && it->F==R[i][j][k].F) R[i][j][k].S=it->S;
            }
            for(int k=0; k<(int)C[i][j].size(); k++){
                auto it=lower_bound(C[i][j+1].begin(),C[i][j+1].end(),mp(C[i][j][k].F,-1));
                if(it!=C[i][j+1].end() && it->F==C[i][j][k].F) C[i][j][k].S=it->S;
            }
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            for(int k=0; k<(int)C[i][j].size(); k++){
                upd(C[i][j][k].F,1);
            }
            sort(C[i][j].begin(),C[i][j].end(),[&](const pii &a, const pii &b){return a.S<b.S;});
            int p=0;
            for(int k=0; k<(int)R[i][j].size(); k++){
                while(p<(int)C[i][j].size() && C[i][j][p].S<R[i][j][k].F){
                    upd(C[i][j][p].F,-1);
                    p++;
                }
                ans+=get(R[i][j][k].S);
            }
            while(p<(int)C[i][j].size()){
                upd(C[i][j][p].F,-1);
                p++;
            }
        }
    }
    return ans;
}

• 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