Submission #1225375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225375		Hamed_Ghaffari	Rectangles (IOI19_rect)	C++20	100 / 100	1795 ms	756140 KiB

rect

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

using ll = long long;
#define ii int32_t
#define int int16_t
using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 2501;

int n, m;
vector<pii> vr[MXN][MXN], vd[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, 0});
                szx--;
            }
            if(szx) {
                if(j+1<stk[szx-1]) vr[i][j+1].push_back({stk[szx-1]-1, 0});
                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();
            for(int j=0, r; j<sz; j++) {
                r = vr[i][l][j].X;
                if(L[l][r]==i+1) {
                    vr[i][l][j].Y = R[l][r];
                    L[l][r] = i;
                }
                else
                    vr[i][l][j].Y = 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, 0});
                szx--;
            }
            if(szx) {
                if(i+1<stk[szx-1]) vd[i+1][j].push_back({stk[szx-1]-1, 0});
                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();
            for(int i=0, r; i<sz; i++) {
                r = vd[l][j][i].X;
                if(L[l][r]==j+1) {
                    vd[l][j][i].Y = R[l][r];
                    L[l][r] = j;
                }
                else
                    vd[l][j][i].Y = 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 vr[i][j][x].Y<vr[i][j][y].Y;
            });
            int p1=0, p2=0;
            while(p1<sr && p2<sd) {
                if(vd[i][j][p2].X<=vr[i][j][ord[p1]].Y)
                    updx(vd[i][j][p2++].Y, 1);
                else
                    ans += p2-getx(vr[i][j][ord[p1++]].X-1);
            }
            while(p1<sr)
                ans += p2-getx(vr[i][j][ord[p1++]].X-1);
            while((--p2)>=0)
                updx(vd[i][j][p2].Y, -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: 28 / 28