Submission #1225372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225372		Hamed_Ghaffari	Rectangles (IOI19_rect)	C++20	72 / 100	1611 ms	1052092 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define ii int32_t
#define int int16_t


const int MXN = 2501;

int n, m;
vector<int> vr[MXN][MXN], vd[MXN][MXN], wr[MXN][MXN], wd[MXN][MXN];
int L[MXN][MXN], R[MXN][MXN];
int stk[MXN], szx, ord[MXN];

int fen[MXN];
inline void updx(int p, int x) {
    for(++p; p<=m; p+=p&-p) fen[p] += x;
}
inline int getx(int p) {
    int res=0;
    for(++p; p; p-=p&-p) res += fen[p];
    return res;
}

ll count_rectangles(vector<vector<ii>> a) {
    n = a.size(), m = a[0].size();
    if(n<=2 || m<=2) return 0;

    for(int l=0; l<m; l++)
        for(int r=l; r<m; r++)
            L[l][r] = n+5;
    for(int i=n-2; i>=1; i--) {
        szx = 0;
        for(int j=m-1; j>=0; j--) {
            while(szx &&  a[i][stk[szx-1]]<a[i][j]) {
                if(j+1<stk[szx-1]) vr[i][j+1].push_back(stk[szx-1]-1);
                szx--;
            }
            if(szx) {
                if(j+1<stk[szx-1]) vr[i][j+1].push_back(stk[szx-1]-1);
                if(a[i][stk[szx-1]]==a[i][j]) szx--;
            }
            stk[szx++] = j;
        }

        for(int l=1, sz; l+1<m; l++) {
            sz = vr[i][l].size();
            wr[i][l].resize(sz);
            for(int j=0, r; j<sz; j++) {
                r = vr[i][l][j];
                if(L[l][r]==i+1) {
                    wr[i][l][j] = R[l][r];
                    L[l][r] = i;
                }
                else
                    wr[i][l][j] = L[l][r] = R[l][r] = i;
            }
        }
    }

    for(int l=0; l<n; l++)
        for(int r=l; r<n; r++)
            L[l][r] = m+5;
    for(int j=m-2; j>=1; j--) {
        szx = 0;
        for(int i=n-1; i>=0; i--) {
            while(szx && a[stk[szx-1]][j]<a[i][j]) {
                if(i+1<stk[szx-1]) vd[i+1][j].push_back(stk[szx-1]-1);
                szx--;
            }
            if(szx) {
                if(i+1<stk[szx-1]) vd[i+1][j].push_back(stk[szx-1]-1);
                if(a[stk[szx-1]][j]==a[i][j]) szx--;
            }
            stk[szx++] = i;
        }

        for(int l=1, sz; l+1<n; l++) {
            sz = vd[l][j].size();
            wd[l][j].resize(sz);
            for(int i=0, r; i<sz; i++) {
                r = vd[l][j][i];
                if(L[l][r]==j+1) {
                    wd[l][j][i] = R[l][r];
                    L[l][r] = j;
                }
                else
                    wd[l][j][i] = L[l][r] = R[l][r] = j;
            }
        }
    }

    ll ans = 0;
    for(int i=0, sr, sd; i<n; i++)
        for(int j=0; j<m; j++) {
            sr = vr[i][j].size();
            sd = vd[i][j].size();
            iota(ord, ord+sr, 0);
            sort(ord, ord+sr, [&](int x, int y) {
                return wr[i][j][x]<wr[i][j][y];
            });
            int p1=0, p2=0;
            while(p1<sr && p2<sd) {
                if(vd[i][j][p2]<=wr[i][j][ord[p1]])
                    updx(wd[i][j][p2++], 1);
                else
                    ans += p2-getx(vr[i][j][ord[p1++]]-1);
            }
            while(p1<sr)
                ans += p2-getx(vr[i][j][ord[p1++]]-1);
            while((--p2)>=0)
                updx(wd[i][j][p2], -1);
        }
    
    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: 0 / 28