Submission #561338

#	Time	Username	Problem	Language	Result	Execution time	Memory
561338		fcmalkcin	Rectangles (IOI19_rect)	C++17	0 / 100	40 ms	48516 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=2e2+5e2+10;
const ll mod=1e9+7  ;
const ll base=1e18;


/// i believe myself
/// goal 2/7

bool dd[maxn][maxn];

vector<pair<ll,pll>> adj[maxn];
vector<ll> fwt[maxn][maxn];
vector<ll> vt[maxn][maxn];
//#include "rect.h"

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;
        i=j;
    }
}

Compilation message (stderr)

rect.cpp:14:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const ll base=1e18;
      |               ^~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:71:19: 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]
   71 |     for (int i=0;i<vt.size();i++)
      |                  ~^~~~~~~~~~
rect.cpp:74: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]
   74 |         while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j].ss) j++;
      |                ~^~~~~~~~~~
rect.cpp:123:19: 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]
  123 |     for (int i=0;i<vt.size();i++)
      |                  ~^~~~~~~~~~
rect.cpp:126: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]
  126 |         while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j].ss) j++;
      |                ~^~~~~~~~~~
rect.cpp:128:12: warning: unused variable 'l' [-Wunused-variable]
  128 |         ll l=vt[i].ss;
      |            ^
rect.cpp:129:12: warning: unused variable 'r' [-Wunused-variable]
  129 |         ll r=vt[j].ss;
      |            ^
rect.cpp:130:14: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  130 |         auto p=vt[j].ff;
      |              ^
rect.cpp:32:26: warning: control reaches end of non-void function [-Wreturn-type]
   32 |     vector<pair<pll,ll>> vt;
      |                          ^~

• 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