Submission #294420

#	Time	Username	Problem	Language	Result	Execution time	Memory
294420		Pajaraja	Rectangles (IOI19_rect)	C++17	72 / 100	5090 ms	884920 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define MAXN 2507
using namespace std;
vector<short> s[MAXN][MAXN];
vector<bool> v[MAXN][MAXN];
vector<int> ind[MAXN];
short bit[MAXN][MAXN],qx[2*MAXN*MAXN],qy[2*MAXN*MAXN],ql[2*MAXN*MAXN],qt[2*MAXN*MAXN],lge[MAXN];
stack<int> st;
int cnt;
inline void upd(int k,int u,int v)
{
    while(u<MAXN)
    {
        bit[k][u]+=v;
        u+=u&(-u);
    }
}
inline int fnd(int k,int u)
{
    int sol=0;
    while(u)
    {
        sol+=bit[k][u];
        u-=u&(-u);
    }
    return sol;
}
bool cmp(int a,int b) {return ql[a]<ql[b];}
long long count_rectangles(std::vector<std::vector<int> > a)
{
    int n=a.size(),m=a[0].size();
    long long sol=0;
    for(int i=1;i<n-1;i++)
    {
        for(int j=0;j<m;j++)
        {
            while(!st.empty() && a[i][st.top()]<a[i][j]) st.pop();
            if(!st.empty() && st.top()+1!=j) {s[j-1][i].push_back(st.top()+1); v[j-1][i].push_back(false);}
            if(!st.empty()) lge[j]=st.top();
            else lge[j]=-1;
            st.push(j);
        }
        while(!st.empty()) st.pop();
        for(int j=m-1;j>=0;j--)
        {
            while(!st.empty() && a[i][st.top()]<a[i][j]) st.pop();
            if(!st.empty() && st.top()-1!=j && lge[st.top()]!=j) {s[st.top()-1][i].push_back(j+1); v[st.top()-1][i].push_back(false);}
            st.push(j);
        }
        while(!st.empty()) st.pop();
    }
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) sort(s[j][i].begin(),s[j][i].end());
    for(int j=1;j<m-1;j++)
    {
        for(int i=1;i<n;i++)
        {
            for(int it=0;it<s[j][i].size();it++) if(!v[j][i][it])
            {
                int br=s[j][i][it];
                for(int k=i;k<n-1;k++)
                {
                    int kt=lower_bound(s[j][k].begin(),s[j][k].end(),br)-s[j][k].begin();
                    if(kt==s[j][k].size() || s[j][k][kt]!=br) break;
                    else {if(k!=i) v[j][k][kt]=true; qx[cnt]=br; qy[cnt]=j; ql[cnt]=2*i+1; ind[k].push_back(cnt++);}
                }
            }
            s[j][i].clear(); v[j][i].clear();
        }
    }
    for(int i=1;i<m-1;i++)
    {
        for(int j=0;j<n;j++)
        {
            while(!st.empty() && a[st.top()][i]<a[j][i]) st.pop();
            if(!st.empty() && st.top()+1!=j) {s[j-1][i].push_back(st.top()+1); v[j-1][i].push_back(false);}
            if(!st.empty()) lge[j]=st.top();
            else lge[j]=-1;
            st.push(j);
        }
        while(!st.empty()) st.pop();
        for(int j=n-1;j>=0;j--)
        {
            while(!st.empty() && a[st.top()][i]<a[j][i]) st.pop();
            if(!st.empty() && st.top()-1!=j && lge[st.top()]!=j) {s[st.top()-1][i].push_back(j+1); v[st.top()-1][i].push_back(false);}
            st.push(j);
        }
        while(!st.empty()) st.pop();
    }
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) sort(s[i][j].begin(),s[i][j].end());
    for(int i=1;i<n-1;i++)
    {
        for(int j=1;j<m;j++)
        {
            for(int it=0;it<s[i][j].size();it++) if(!v[i][j][it])
            {
                int br=s[i][j][it];
                for(int k=j+1;k<m;k++)
                {
                    int kt=lower_bound(s[i][k].begin(),s[i][k].end(),br)-s[i][k].begin();
                    if(kt==s[i][k].size() || s[i][k][kt]!=br) {qx[cnt]=j; qy[cnt]=k-1; ql[cnt]=2*br+2; ind[i].push_back(cnt++); break;}
                    else v[i][k][kt]=true;
                }
            }
        }
    }
    for(int i=1;i<n-1;i++)
    {
        sort(ind[i].begin(),ind[i].end(),cmp);
        for(int j=0;j<ind[i].size();j++)
        {
            if(ql[ind[i][j]]&1) upd(qx[ind[i][j]],qy[ind[i][j]],1);
            else for(int k=qx[ind[i][j]];k<=qy[ind[i][j]];k++) sol+=fnd(k,qy[ind[i][j]]);
        }
        for(int j=0;j<ind[i].size();j++) if(ql[ind[i][j]]&1) upd(qx[ind[i][j]],qy[ind[i][j]],-1);
        ind[i].clear();
    }
	return sol;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:58:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for(int it=0;it<s[j][i].size();it++) if(!v[j][i][it])
      |                          ~~^~~~~~~~~~~~~~~
rect.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |                     if(kt==s[j][k].size() || s[j][k][kt]!=br) break;
      |                        ~~^~~~~~~~~~~~~~~~
rect.cpp:95:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             for(int it=0;it<s[i][j].size();it++) if(!v[i][j][it])
      |                          ~~^~~~~~~~~~~~~~~
rect.cpp:101:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |                     if(kt==s[i][k].size() || s[i][k][kt]!=br) {qx[cnt]=j; qy[cnt]=k-1; ql[cnt]=2*br+2; ind[i].push_back(cnt++); break;}
      |                        ~~^~~~~~~~~~~~~~~~
rect.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(int j=0;j<ind[i].size();j++)
      |                     ~^~~~~~~~~~~~~~
rect.cpp:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for(int j=0;j<ind[i].size();j++) if(ql[ind[i][j]]&1) upd(qx[ind[i][j]],qy[ind[i][j]],-1);
      |                     ~^~~~~~~~~~~~~~

• 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: 0 / 28