Submission #561359

#	Time	Username	Problem	Language	Result	Execution time	Memory
561359		fcmalkcin	Rectangles (IOI19_rect)	C++17	0 / 100	163 ms	302680 KiB

rect

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

#define ll  int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e3+5e2+10;
//const ll maxn=50;
const ll mod=1e9+7  ;
const ll base=1e18;


/// i believe myself
/// goal 2/7
#include "rect.h"

bool dd[maxn][maxn];

vector<pair<ll,pll>> adj[maxn];
vector<pair<ll,pll>> adjq[maxn];
vector<ll> fwt[maxn][maxn];
vector<ll> vtfwt[maxn][maxn];
ll get(ll x,ll y,ll p)
{
    p=lower_bound(vtfwt[x][y].begin(),vtfwt[x][y].end(),p)-vtfwt[x][y].begin()+1;
    ll len=vtfwt[x][y].size();
    p=min(p,len);
    ll ans=0;
    for (int i=p;i; i -= i&(-i))
        ans+=fwt[x][y][i];
    return ans;
}
void update1(ll x,ll y,ll p,ll diff)
{
    p=lower_bound(vtfwt[x][y].begin(),vtfwt[x][y].end(),p)-vtfwt[x][y].begin()+1;
    ll len=vtfwt[x][y].size();
    for (int i=p+1; i<=len; i+= i&(-i))
        fwt[x][y][i]-=diff;
    for (int i=1; i<=len; i+= i&(-i))
        fwt[x][y][i]+=diff;
}
void update(ll p,ll l,ll r,ll diff)
{
    for (int t=l; t<=r; t++)
    {
        update1(p,t,r,diff);
    }
}
long long count_rectangles(vector<vector<ll>> a)
{
    ll n=a.size();
    ll m=a[0].size();
    if (min(n,m)<=2)
        return 0;
    vector<pair<pll,ll>> vt;
    for (int i=1; i+1<n; i++)
    {
        stack<ll> st;
        vector<pll> vt1;
        for (int j=0; j<m; j++)
        {
            while (st.size()&&a[i][st.top()]<a[i][j])
                st.pop();
            if (st.size())
            {
                ll h=st.top();
                if (!dd[h][j]&&h+1<j)
                {
                    dd[h][j]=1;
                    vt.pb(make_pair(make_pair(h,j),i));
                    vt1.pb(make_pair(h,j));
                }
            }
            st.push(j);
        }
        while (st.size())
            st.pop();
        for (int j=m-1; j>=0; j--)
        {
            while (st.size()&&a[i][st.top()]<a[i][j])
                st.pop();
            if (st.size())
            {
                ll h=st.top();
                if (!dd[j][h]&&j+1<h)
                {
                    dd[j][h]=1;
                    vt.pb(make_pair(make_pair(j,h),i));
                    vt1.pb(make_pair(j,h));
                }
            }
            st.push(j);
        }
        for (auto p:vt1)
            dd[p.ff][p.ss]=false;
    }
    sort(vt.begin(),vt.end());
    for (int i=0; i<vt.size(); i++)
    {
        ll j=i+1;
        while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j-1].ss)
            j++;
        j--;
        auto p=vt[j].ff;
        p.ff++;
        p.ss--;
        ll l=vt[i].ss-1;
        ll r=vt[j].ss+1;
        adj[l].pb(make_pair(r,p));
        i=j;
    }
    vt.clear();
    for (int j=0; j<m; j++)
    {
        stack<ll> st;
        vector<pll> vt1;
        for (int i=0; i<n; i++)
        {
            while (st.size()&&a[st.top()][j]<a[i][j])
                st.pop();
            if (st.size())
            {
                ll h=st.top();
                if (!dd[h][i]&&h+1<i)
                {
                    dd[h][i]=1;
                    vt.pb(make_pair(make_pair(h,i),j));
                    vt1.pb(make_pair(h,i));
                }
            }
            st.push(i);
        }
        while (st.size())
            st.pop();
        for (int i=n-1; i>=0; i--)
        {
            while (st.size()&&a[st.top()][j]<a[i][j])
                st.pop();
            if (st.size())
            {
                ll h=st.top();
                if (!dd[i][h]&&i+1<h)
                {
                    dd[i][h]=1;
                    vt.pb(make_pair(make_pair(i,h),j));
                    vt1.pb(make_pair(i,h));
                }
            }
            st.push(i);
        }
        for (auto p:vt1)
            dd[p.ff][p.ss]=false;
    }
    sort(vt.begin(),vt.end());
    for (int i=0; i<vt.size(); i++)
    {
        ll j=i+1;
        while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j-1].ss)
            j++;
        j--;
        ll l=vt[i].ss;
        ll r=vt[j].ss;
        auto p=vt[j].ff;
        for (int t=l; t<=r; t++)
        {
            ll idnw=p.ss;
            vtfwt[idnw][t].pb(r);
        }
        i=j;
    }
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            if (vtfwt[i][j].size())
            {

            sort(vtfwt[i][j].begin(),vtfwt[i][j].end());
            vtfwt[i][j].resize(unique(vtfwt[i][j].begin(),vtfwt[i][j].end())-vtfwt[i][j].begin());
            ll len=vtfwt[i][j].size();
            fwt[i][j]=vector<ll> (len+3,0);
            }
        }
    }
    for (int i=0; i<vt.size(); i++)
    {
        ll j=i+1;
        while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j-1].ss)
            j++;
        j--;
        ll l=vt[i].ss;
        ll r=vt[j].ss;
        auto p=vt[j].ff;
        update(p.ss,l,r,1);
        adjq[p.ff+1].pb(make_pair(p.ss,make_pair(l,r)));
        i=j;
    }
    long long ans=0;
    for (int i=0; i<n; i++)
    {
        for (auto p:adjq[i])
        {
            update(p.ff,p.ss.ff,p.ss.ss,-1);
        }
        for (auto to:adj[i])
        {
            ll r=to.ff;
            auto p=to.ss;
            for (int t=i;t<=r;t++)
            {
                ans+=get(t,p.ff,p.ss);
            }
        }
    }
    return ans;
}


/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    vector<vector<ll>> a;
    ll n, m;
    cin>> n>> m;
    for (int i=0;i<n;i++)
    {
        vector<ll> vt;
        for (int j=0;j<m;j++)
        {
            ll x;
            cin>> x;
            vt.pb(x);
        }
        a.pb(vt);
    }
    cout <<count_rectangles(a)<<endl;
}*/

/*
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:15:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const ll base=1e18;
      |               ^~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for (int i=0; i<vt.size(); i++)
      |                   ~^~~~~~~~~~
rect.cpp:106:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j-1].ss)
      |                ~^~~~~~~~~~
rect.cpp:160:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for (int i=0; i<vt.size(); i++)
      |                   ~^~~~~~~~~~
rect.cpp:163:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j-1].ss)
      |                ~^~~~~~~~~~
rect.cpp:190:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |     for (int i=0; i<vt.size(); i++)
      |                   ~^~~~~~~~~~
rect.cpp:193:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |         while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j-1].ss)
      |                ~^~~~~~~~~~

• 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