Submission #231132

#	Time	Username	Problem	Language	Result	Execution time	Memory
231132		achibasadzishvili	Rectangles (IOI19_rect)	C++14	0 / 100	1658 ms	466592 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[x][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;
        }
    }
    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 << " " << l[x][y] << " " << z << '\n';
                    if(p && k){
                    //    cout << " +1";
                        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][y + 1] <= a[z][y + 1] && qve[x - 1][y + 1] >= r[x][y] - y - 1)p = 1;
                    if(a[x - 1][y + 1] >= a[z][y + 1] && ze[z][y + 1] >= r[x][y] - y - 1)p = 1;
                //    cout << x << " " << y << " " << r[x][y] << " " << z << " " << rig[x][y] << " " << p << '\n';
                    if(p && k){
                    //    cout << " +";
                        ans++;
                    }
                    //cout << '\n';
                }
            }
        }
    }
    return ans;
}
/*
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
*/

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:123: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:140: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: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28