Submission #750948

#	Time	Username	Problem	Language	Result	Execution time	Memory
750948		bachhoangxuan	Rectangles (IOI19_rect)	C++17	59 / 100	1556 ms	1048576 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
const int maxl=12;
struct BIT{
    int n;
    vector<int> bit;
    BIT(int N):n(N){
        bit.assign(n+1,0);
    }
    void update(int x,int val){
        for(int i=x;i<=n;i+=(i&(-i))) bit[i]+=val;
    }
    int query(int x){
        int res=0;
        for(int i=x;i>=1;i-=(i&(-i))) res+=bit[i];
        return res;
    }
};
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/
long long count_rectangles(std::vector<std::vector<int> > a) {
    int n=(int)a.size(),m=(int)a[0].size();
	vector<vector<vector<int>>> pos(m,vector<vector<int>>(m,vector<int>()));
    for(int i=1;i<n-1;i++){
        vector<int> l(m),r(m),v;
        for(int j=0;j<m;j++){
            while(!v.empty() && a[i][v.back()]<=a[i][j]) v.pop_back();
            if(!v.empty()) l[j]=v.back();
            else l[j]=-1;
            v.push_back(j);
        }
        v.clear();
        for(int j=m-1;j>=0;j--){
            while(!v.empty() && a[i][v.back()]<=a[i][j]) v.pop_back();
            if(!v.empty()) r[j]=v.back();
            else r[j]=m;
            v.push_back(j);
        }
        for(int j=0;j<m;j++){
            if(l[j]>=0 && r[j]<m){
                int lt=l[j]+1,rt=r[j]-1;
                if(pos[lt][rt].empty() || pos[lt][rt].back()!=i) pos[lt][rt].push_back(i);
            }
        }
    }
    vector<int> lg2(m+1,0);
    for(int i=2;i<=m;i++) lg2[i]=lg2[i/2]+1;
    vector<vector<vector<int>>> down(n,vector<vector<int>>(m,vector<int>(maxl,0))),up(n,vector<vector<int>>(m,vector<int>(maxl,0)));
    for(int i=0;i<m;i++){
        vector<int> v={0};
        for(int j=1;j<n;j++){
            while(!v.empty() && a[j][i]>a[v.back()][i]) v.pop_back();
            if(v.empty()) up[j-1][i][0]=0;
            else up[j-1][i][0]=v.back()+1;
            v.push_back(j);
        }
        v={n-1};
        for(int j=n-2;j>=0;j--){
            while(!v.empty() && a[j][i]>a[v.back()][i]) v.pop_back();
            if(v.empty()) down[j+1][i][0]=n-1;
            else down[j+1][i][0]=v.back()-1;
            v.push_back(j);
        }
    }
    /*
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) cout << down[i][j][0] << ' ';
        cout << '\n';
    }
    */
    for(int k=1;k<maxl;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<=m-(1<<k);j++){
                up[i][j][k]=max(up[i][j][k-1],up[i][j+(1<<(k-1))][k-1]);
                down[i][j][k]=min(down[i][j][k-1],down[i][j+(1<<(k-1))][k-1]);
            }
        }
    }
    auto Min_down = [&](int x,int l,int r){
        int p=lg2[r-l+1];
        return min(down[x][l][p],down[x][r-(1<<p)+1][p]);
    };
    auto Max_up = [&](int x,int l,int r){
        int p=lg2[r-l+1];
        return max(up[x][l][p],up[x][r-(1<<p)+1][p]);
    };
    long long ans=0;
    vector<vector<int>> lst(n+1,vector<int>());
    BIT bit(n+1);
    auto cal = [&](int l,int r,vector<int> cur){
        int cnt=0,Max=cur.back(),Min=cur.front();
        //cout << '*' << l << ' ' << r << '\n';
        for(int id:cur){
            int rt=min(Max,Min_down(id,l,r)),lt=max(Min,Max_up(id,l,r));
            //cout << id << ' ' << lt << ' ' << rt << '\n';
            lst[rt+1].push_back(id);
            bit.update(id,1);cnt++;
            for(int x:lst[id]) bit.update(x,-1),cnt--;
            ans+=cnt-bit.query(lt-1);
        }
        for(int x:lst[Max+1]) bit.update(x,-1);
        for(int i=Min;i<=Max+1;i++) lst[i].clear();
        //cout << ans << '\n';
    };
    for(int l=1;l<m-1;l++){
        for(int r=l;r<m-1;r++){
            if(pos[l][r].empty()) continue;
            vector<int> cur;
            for(int id:pos[l][r]){
                if(cur.empty() || cur.back()+1==id) cur.push_back(id);
                else cal(l,r,cur),cur={id};
            }
            if(!cur.empty()) cal(l,r,cur);

        }
    }
    return ans;
}

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