Submission #760375

#	Time	Username	Problem	Language	Result	Execution time	Memory
760375		bgnbvnbv	Rectangles (IOI19_rect)	C++14	100 / 100	1167 ms	351260 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2500+10;
const ll inf=1e18;
const ll mod=1e9+7;
vector<int>dq[maxN];
vector<ll>vec[maxN];
ll bit[maxN][maxN];
void update(ll t,ll i,ll v)
{
    while(i<=t)
    {
        bit[t][i]+=v;
        i+=i&(-i);
    }
}
ll get(ll t,ll i)
{
    ll aa=0;
    while(i>0)
    {
        aa+=bit[t][i];
        i-=i&(-i);
    }
    return aa;
}
struct qq
{
    ll x,y,en;
};
vector<qq>in[maxN];
ll count_rectangles(vector<vector<int>> a)
{
    ll n=a.size();
    ll m=a[0].size();
    for(int i=0;i<n;i++)
    {
        dq[i].pb(0);
    }
    for(int j=1;j<m;j++)
    {
        for(int i=0;i<n;i++)
        {
            while(dq[i].size()>0&&a[i][j]>a[i][dq[i].back()])
            {
                if(dq[i].back()<=j-2) vec[dq[i].back()+1].pb(i);
                dq[i].pop_back();
            }
            if(dq[i].size())
            {
                if(dq[i].back()<=j-2) vec[dq[i].back()+1].pb(i);
                if(a[i][j]==a[i][dq[i].back()]) dq[i].pop_back();
            }
            dq[i].pb(j);
        }
        for(int i=0;i<j;i++)
        {
            ll l;
            for(int k=0;k<vec[i].size();k++)
            {
                if(k==0)
                {
                    l=vec[i][k];
                }
                else if(vec[i][k]>vec[i][k-1]+1)
                {
                    in[l].pb({i,j-1,vec[i][k-1]});
                    l=vec[i][k];
                }
            }
            if(vec[i].size()>0) in[l].pb({i,j-1,vec[i].back()});
            vec[i].clear();
        }
    }


    for(int i=0;i<m;i++)
    {
        dq[i].clear();
        dq[i].pb(0);
    }
    vector<pair<ll,qq>>tap,cc;
    ll ans=0;
    for(int i=1;i<n;i++)
    {
        for(auto zz:in[i-1])
        {
            tap.pb({i-1,zz});
        }
        cc.clear();
        for(auto zz:tap)
        {
            if(zz.se.en>=i-1) cc.pb(zz);
        }
        swap(tap,cc);
        for(int j=0;j<m;j++)
        {
            while(dq[j].size()>0&&a[i][j]>a[dq[j].back()][j])
            {
                if(dq[j].back()+1<=i-1) vec[dq[j].back()+1].pb(j);
                dq[j].pop_back();
            }
            if(dq[j].size()>0)
            {
                if(dq[j].back()+1<=i-1) vec[dq[j].back()+1].pb(j);
                if(a[dq[j].back()][j]==a[i][j]) dq[j].pop_back();
            }
            dq[j].pb(i);
        }
        ll q=0;
        for(int j=0;j<i;j++)
        {
            ll l;
            while(q<tap.size()&&tap[q].fi<=j)
            {
                update(tap[q].se.y,tap[q].se.x,1);
                q++;
            }
            for(int k=0;k<vec[j].size();k++)
            {
                if(k==0)
                {
                    l=vec[j][k];
                }
                else if(vec[j][k]>vec[j][k-1]+1)
                {
                    l=vec[j][k];
                }
                ans+=get(vec[j][k],vec[j][k])-get(vec[j][k],l-1);
            }
            vec[j].clear();
        }
        q--;
        while(q>=0)
        {
            update(tap[q].se.y,tap[q].se.x,-1);
            q--;
        }
    }
    return ans;
}
/*void solve()
{
    cout << count_rectangles({{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}});
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}*/

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for(int k=0;k<vec[i].size();k++)
      |                         ~^~~~~~~~~~~~~~
rect.cpp:122:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, qq> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             while(q<tap.size()&&tap[q].fi<=j)
      |                   ~^~~~~~~~~~~
rect.cpp:127:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |             for(int k=0;k<vec[j].size();k++)
      |                         ~^~~~~~~~~~~~~~

• 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