Submission #561353

#	Time	Username	Problem	Language	Result	Execution time	Memory
561353		fcmalkcin	Rectangles (IOI19_rect)	C++17	0 / 100	169 ms	302988 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)
{
    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)
{
    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].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=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[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].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++)
        {
            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].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;
}

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:99: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]
   99 |     for (int i=0; i<vt.size(); i++)
      |                   ~^~~~~~~~~~
rect.cpp:102: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]
  102 |         while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j].ss)
      |                ~^~~~~~~~~~
rect.cpp:156: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]
  156 |     for (int i=0; i<vt.size(); i++)
      |                   ~^~~~~~~~~~
rect.cpp:159: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]
  159 |         while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j].ss)
      |                ~^~~~~~~~~~
rect.cpp:182: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]
  182 |     for (int i=0; i<vt.size(); i++)
      |                   ~^~~~~~~~~~
rect.cpp:185: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]
  185 |         while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j].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