Submission #231144

#	Time	Username	Problem	Language	Result	Execution time	Memory
231144		achibasadzishvili	Rectangles (IOI19_rect)	C++14	100 / 100	4225 ms	831368 KiB

rect

#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
vector<ll>vec[2505][2505];
ll l[2505][2505],r[2505][2505],dow[2505][2505],up[2505][2505];
ll qve[2505][2505],ze[2505][2505];
ll rig[2505][2505],lef[2505][2505];
vector<pair<ll,ll> >row[2505],col[2505];
long long count_rectangles(vector<vector<int> >a){
    ll n = (ll)a.size();
    ll m = (ll)a[0].size();
    stack<pair<ll,ll> >st;
    for(int i=0; i<n; i++){
        while(st.size())st.pop();
        for(int j=0; j<m; j++){
            while(st.size() && a[i][j] > st.top().f)st.pop();
            l[i][j] = -1;
            if(st.size())l[i][j] = st.top().s;
            st.push(mp(a[i][j] , j));
        }
        while(st.size())st.pop();
        for(int j=m - 1; j>=0; j--){
            while(st.size() && a[i][j] > st.top().f)st.pop();
            r[i][j] = m + 1;
            if(st.size())r[i][j] = st.top().s;
            st.push(mp(a[i][j] , j));
        }
        for(int j=0; j<m; j++){
            if(l[i][j] != -1){
                // l[i][j] , j is possible
                row[i].pb(mp(l[i][j] , j));
            }
            if(r[i][j] != m + 1){
                // j r[i][j] is possible
                row[i].pb(mp(j , r[i][j]));
            }
        }
    }
    
    for(int i=0; i<m; i++){
        while(st.size())st.pop();
        for(int j=0; j<n; j++){
            while(st.size() && a[j][i] > st.top().f)st.pop();
            up[j][i] = -1;
            if(st.size())up[j][i] = st.top().s;
            st.push(mp(a[j][i] , j));
        }
        while(st.size())st.pop();
        for(int j=n - 1; j>=0; j--){
            while(st.size() && a[j][i] > st.top().f)st.pop();
            dow[j][i] = n + 1;
            if(st.size())dow[j][i] = st.top().s;
            st.push(mp(a[j][i] , j));
        }
        for(int j=0; j<n; j++){
            if(up[j][i] != -1){
                vec[up[j][i]][i].pb(j);
                col[i].pb(mp(up[j][i] , j));
            }
            if(dow[j][i] != n + 1){
                if(a[j][i] != a[dow[j][i]][i])
                vec[j][i].pb(dow[j][i]);
                col[i].pb(mp(j , dow[j][i]));
            }
        }
    }
    
    for(int i=0; i<m; i++){
        for(int j=0; j<col[i].size(); j++){
            ll x = col[i][j].f;
            ll y = col[i][j].s;
            bool ok = 0;
            if(a[x][i] <= a[y][i])
                qve[x][i] = 1;
            if(a[x][i] >= a[y][i])
                ze[y][i] = 1;
            if(i == 0){
                continue;
            }
            if(a[x][i] <= a[y][i] && a[x][i - 1] <= a[y][i - 1] && dow[x][i - 1] == y)
                qve[x][i] = qve[x][i - 1] + 1;
            if(a[x][i] >= a[y][i] && a[x][i - 1] <= a[y][i - 1] && dow[x][i - 1] == y)
                ze[y][i] = qve[x][i - 1] + 1;
            if(a[x][i] <= a[y][i] && a[x][i - 1] >= a[y][i - 1] && up[y][i - 1] == x)
                qve[x][i] = ze[y][i - 1] + 1;
            if(a[x][i] >= a[y][i] && a[x][i - 1] >= a[y][i - 1] && up[y][i - 1] == x)
                ze[y][i] = ze[y][i - 1] + 1;
        }
    }
    
    for(int i=n - 1; i>=0; i--){
        for(int j=0; j<row[i].size(); j++){
            ll x = row[i][j].f;
            ll y = row[i][j].s;
            bool ok = 0;
            if(a[i][x] <= a[i][y])
                rig[i][x] = 1;
            if(a[i][x] >= a[i][y])
                lef[i][y] = 1;
            if(i == n - 1){
                continue;
            }
            if(a[i][x] <= a[i][y] && a[i + 1][x] <= a[i + 1][y] && r[i + 1][x] == y)
                rig[i][x] = rig[i + 1][x] + 1;
            if(a[i][x] >= a[i][y] && a[i + 1][x] <= a[i + 1][y] && r[i + 1][x] == y)
                lef[i][y] = rig[i + 1][x] + 1;
            if(a[i][x] <= a[i][y] && a[i + 1][x] >= a[i + 1][y] && l[i + 1][y] == x)
                rig[i][x] = lef[i + 1][y] + 1;
            if(a[i][x] >= a[i][y] && a[i + 1][x] >= a[i + 1][y] && l[i + 1][y] == x)
                lef[i][y] = lef[i + 1][y] + 1;
        }
    }
    //cout << qve[1][2] << "<--\n";
    ll ans = 0;
    for(int x=1; x<n-1; x++){
        for(int y=0; y<m; y++){
            // cout << x << " " << y << " " << l[x][y] << " " << r[x][y] << '\n';
            if(l[x][y] != -1 && a[x][l[x][y]] >= a[x][y] && l[x][y] < y - 1){
                //cout << x - 1 << " --- " << y - 1 << '\n';
                for(int i=0; i<vec[x - 1][y - 1].size(); i++){
                    ll z = vec[x - 1][y - 1][i];
                    if(z == x)continue;
                    bool k = 0 , p = 0;
                    if(lef[x][y] >= z - x)k = 1;
                    if(a[x - 1][y - 1] <= a[z][y - 1] && qve[x - 1][y - 1] >= y - l[x][y] - 1)p = 1;
                    if(a[x - 1][y - 1] >= a[z][y - 1] && ze[z][y - 1] >= y - l[x][y] - 1)p = 1;
                    //cout << x << " " << y << " " << lef[x][y] << " " << z << '\n';
                    if(p && k){
                        //cout << "- " << x << " " << l[x][y] + 1 << " " << z - 1 << " " << y - 1 << '\n';;
                        ans++;
                    }
                    //cout << '\n';
                }
            }
            if(r[x][y] < m && a[x][r[x][y]] > a[x][y] && r[x][y] > y + 1){
            //    cout << x - 1 << " -- " << y + 1 << '\n';
                for(int i=0; i<vec[x - 1][y + 1].size(); i++){
                    ll z = vec[x - 1][y + 1][i];
                    if(z == x)continue;
                    bool k = 0 , p = 0;
                    if(rig[x][y] >= z - x)k = 1;
                    if(a[x - 1][r[x][y] - 1] <= a[z][r[x][y] - 1] && qve[x - 1][r[x][y] - 1] >= r[x][y] - y - 1 && dow[x-1][r[x][y]-1] == z)p = 1;
                    if(a[x - 1][r[x][y] - 1] >= a[z][r[x][y] - 1] && ze[z][r[x][y] - 1] >= r[x][y] - y - 1 && up[z][r[x][y]-1] == x - 1)p = 1;
                    //cout << x << " " << y << " " << r[x][y] << " " << z << " " << rig[x][y] << " " << p << '\n';
                    if(p && k){
                    //    cout << " +";
                        //cout << "- " << x << " " << y + 1 << " " << z - 1 << " " << r[x][y] - 1 << '\n';;
                        ans++;
                    }
                    //cout << '\n';
                }
            }
        }
    }
    return ans;
}
long long naive(vector<vector<int> >a){
    ll ans = 0;
    for(int x=1; x<(int)a.size() - 1; x++){
        for(int y=1; y<(int)a[0].size() - 1; y++){
            for(int z=x; z<(int)a.size() - 1; z++){
                for(int t=y; t<(int)a[0].size() - 1; t++){
                    bool ok = 1;
                    for(int i=x; i<=z; i++)
                        for(int j=y; j<=t; j++)
                            if(a[i][j] >= a[x - 1][j] || a[i][j] >= a[z + 1][j] || a[i][j] >= a[i][y - 1] || a[i][j] >= a[i][t + 1])
                                ok = 0;
                    ans += (ok == 1);
                }
            }
        }
    }
    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:73:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<col[i].size(); j++){
                      ~^~~~~~~~~~~~~~
rect.cpp:76:18: warning: unused variable 'ok' [-Wunused-variable]
             bool ok = 0;
                  ^~
rect.cpp:96:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<row[i].size(); j++){
                      ~^~~~~~~~~~~~~~
rect.cpp:99:18: warning: unused variable 'ok' [-Wunused-variable]
             bool ok = 0;
                  ^~
rect.cpp:124:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i=0; i<vec[x - 1][y - 1].size(); i++){
                              ~^~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:141:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i=0; i<vec[x - 1][y + 1].size(); i++){
                              ~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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