Submission #146954

#	Time	Username	Problem	Language	Result	Execution time	Memory
146954		nikolapesic2802	Rectangles (IOI19_rect)	C++14	0 / 100	277 ms	196924 KiB

rect

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}

const int N=2501;
vector<int> in;
struct segTree{
    vector<int> mi;
    void init(int l=0,int r=N-1,int i=1)
    {
        if(i==1)
            mi.resize(4*N);
        if(l==r)
        {
            mi[i]=in[l];
            return;
        }
        int m=(l+r)>>1;
        init(l,m,2*i);
        init(m+1,r,2*i+1);
        mi[i]=min(mi[2*i],mi[2*i+1]);
    }
    int get(int qs,int qe,int l=0,int r=N-1,int i=1)
    {
        if(qs>r||qe<l)
            return INT_MAX;
        if(qs<=l&&qe>=r)
            return mi[i];
        int m=(l+r)>>1;
        return min(get(qs,qe,l,m,2*i),get(qs,qe,m+1,r,2*i+1));
    }
}r1[N],r2[N],c1[N],c2[N];
int l[N][N],r[N][N],d[N][N],u[N][N];
ll count_rectangles(vector<vector<int> > a)
{
    int n=a.size(),m=a[0].size(),sol=0;
    vector<pair<int,int> > stk;
    for(int i=0;i<n;i++)
    {
        stk={{INT_MAX,-1}};
        for(int j=0;j<m;j++)
        {
            while(stk.back().f<a[i][j])
                stk.pop_back();
            l[i][j]=j-stk.back().s;
            stk.pb({a[i][j],j});
        }
        stk={{INT_MAX,m}};
        for(int j=m-1;j>=0;j--)
        {
            while(stk.back().f<a[i][j])
                stk.pop_back();
            r[i][j]=stk.back().s-j;
            stk.pb({a[i][j],j});
        }
    }
    for(int j=0;j<m;j++)
    {
        stk={{INT_MAX,-1}};
        for(int i=0;i<n;i++)
        {
            while(stk.back().f<a[i][j])
                stk.pop_back();
            u[i][j]=i-stk.back().s;
            stk.pb({a[i][j],j});
        }
        stk={{INT_MAX,m}};
        for(int i=n-1;i>=0;i--)
        {
            while(stk.back().f<a[i][j])
                stk.pop_back();
            d[i][j]=stk.back().s-i;
            stk.pb({a[i][j],j});
        }
    }
    /*for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            printf("%i ",l[i][j]);
        printf("\n");
    }*/
    for(int j=0;j<m;j++)
    {
        in.clear();
        for(int i=0;i<n;i++)
            in.pb(l[i][j]);
        c1[j].init();
    }
    for(int j=0;j<m;j++)
    {
        in.clear();
        for(int i=0;i<n;i++)
            in.pb(r[i][j]);
        c2[j].init();
    }
    for(int i=0;i<n;i++)
    {
        in.clear();
        for(int j=0;j<m;j++)
            in.pb(u[i][j]);
        r1[i].init();
    }
    for(int i=0;i<n;i++)
    {
        in.clear();
        for(int j=0;j<m;j++)
            in.pb(d[i][j]);
        r2[i].init();
    }
    for(int i=0;i<n;i++)
    {
        stk={{INT_MAX,-1}};
        for(int j=0;j<m;j++)
        {
            while(stk.back().f<=a[i][j])
                stk.pop_back();
            l[i][j]=stk.back().s+1;
            stk.pb({a[i][j],j});
        }
        stk={{INT_MAX,m}};
        for(int j=m-1;j>=0;j--)
        {
            while(stk.back().f<=a[i][j])
                stk.pop_back();
            r[i][j]=stk.back().s-1;
            stk.pb({a[i][j],j});
        }
    }
    for(int j=0;j<m;j++)
    {
        stk={{INT_MAX,-1}};
        for(int i=0;i<n;i++)
        {
            while(stk.back().f<=a[i][j])
                stk.pop_back();
            u[i][j]=stk.back().s+1;
            stk.pb({a[i][j],j});
        }
        stk={{INT_MAX,m}};
        for(int i=n-1;i>=0;i--)
        {
            while(stk.back().f<=a[i][j])
                stk.pop_back();
            d[i][j]=stk.back().s-1;
            stk.pb({a[i][j],j});
        }
    }
    for(int i=1;i<n-1;i++)
        for(int j=1;j<m-1;j++)
            sol+=r[i][j]<n-1&&l[i][j]>0&&u[i][j]>0&&d[i][j]<m-1&&c1[r[i][j]+1].get(u[i][j],d[i][j])>r[i][j]-l[i][j]&&c2[l[i][j]-1].get(u[i][j],d[i][j])>r[i][j]-l[i][j]&&r1[d[i][j]+1].get(l[i][j],r[i][j])>d[i][j]-u[i][j]&&r2[u[i][j]-1].get(l[i][j],r[i][j])>d[i][j]-u[i][j];
    return sol;
}
/*int main()
{
    freopen("in.txt","r",stdin);
    int n,m;
    scanf("%i %i",&n,&m);
    vector<vector<int> > mat(n,vector<int>(m));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%i",&mat[i][j]);
    printf("%lld\n",count_rectangles(mat));
}*/

• 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