Submission #294966

#	Time	Username	Problem	Language	Result	Execution time	Memory
294966		Pajaraja	Rectangles (IOI19_rect)	C++17	100 / 100	3060 ms	272296 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define MAXN 2507
using namespace std;
vector<int> ind[MAXN];
short qx[2*MAXN*MAXN],qy[2*MAXN*MAXN],ql[2*MAXN*MAXN],qt[2*MAXN*MAXN],lge[2][MAXN],rge[2][MAXN],dp[2][MAXN][MAXN];
stack<int> st;
int bit[MAXN][MAXN],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>=k)
    {
        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(),l=0;
    long long sol=0;
    for(int i=0;i<2;i++) for(int j=0;j<MAXN;j++) for(int k=0;k<MAXN;k++) dp[i][j][k]=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)
            {
                if(dp[l^1][st.top()+1][j-1]) dp[l][st.top()+1][j-1]=dp[l^1][st.top()+1][j-1];
                else dp[l][st.top()+1][j-1]=i;
                qx[cnt]=st.top()+1; qy[cnt]=j-1; ql[cnt]=2*dp[l][st.top()+1][j-1]+1; ind[i].push_back(cnt++);
            }
            if(!st.empty()) lge[l][j]=st.top();
            else lge[l][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[l][st.top()]!=j)
            {
                if(dp[l^1][j+1][st.top()-1]) dp[l][j+1][st.top()-1]=dp[l^1][j+1][st.top()-1];
                else dp[l][j+1][st.top()-1]=i;
                qx[cnt]=j+1; qy[cnt]=st.top()-1; ql[cnt]=2*dp[l][j+1][st.top()-1]+1; ind[i].push_back(cnt++);
            }
            if(!st.empty()) rge[l][j]=st.top();
            else rge[l][j]=-1;
            st.push(j);
        }
        while(!st.empty()) st.pop();
        if(i!=1)
        {
            for(int j=0;j<m;j++) if(lge[l^1][j]!=-1) dp[l^1][lge[l^1][j]+1][j-1]=0;
            for(int j=0;j<m;j++) if(rge[l^1][j]!=-1) dp[l^1][j+1][rge[l^1][j]-1]=0;
        }
        l^=1;
    }
    for(int i=0;i<2;i++) for(int j=0;j<MAXN;j++) for(int k=0;k<MAXN;k++) dp[i][j][k]=0;
    for(int i=1;i<m;i++)
    {
        if(i!=m-1) 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)
            {
                if(dp[l^1][st.top()+1][j-1]) dp[l][st.top()+1][j-1]=dp[l^1][st.top()+1][j-1];
                else dp[l][st.top()+1][j-1]=i;
                lge[l][j]=st.top();
            }
            else lge[l][j]=-1;
            st.push(j);
        }
        while(!st.empty()) st.pop();
        if(i!=m-1) 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[l][st.top()]!=j)
            {
                if(dp[l^1][j+1][st.top()-1]) dp[l][j+1][st.top()-1]=dp[l^1][j+1][st.top()-1];
                else dp[l][j+1][st.top()-1]=i;
                rge[l][j]=st.top();
            }
            else rge[l][j]=-1;
            st.push(j);
        }
        while(!st.empty()) st.pop();
        if(i!=1)
        {
            for(int j=0;j<n;j++) if(lge[l^1][j]!=-1 && !dp[l][lge[l^1][j]+1][j-1]) {qx[cnt]=dp[l^1][lge[l^1][j]+1][j-1]; qy[cnt]=i-1; ql[cnt]=2*lge[l^1][j]+4; ind[j-1].push_back(cnt++);}
            for(int j=0;j<n;j++) if(rge[l^1][j]!=-1 && !dp[l][j+1][rge[l^1][j]-1] && lge[l^1][rge[l^1][j]]!=j) {qx[cnt]=dp[l^1][j+1][rge[l^1][j]-1]; qy[cnt]=i-1; ql[cnt]=2*j+4; ind[rge[l^1][j]-1].push_back(cnt++);}
            for(int j=0;j<n;j++) if(lge[l^1][j]!=-1) dp[l^1][lge[l^1][j]+1][j-1]=0;
            for(int j=0;j<n;j++) if(rge[l^1][j]!=-1) dp[l^1][j+1][rge[l^1][j]-1]=0;
        }
        l^=1;
    }
    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:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(int j=0;j<ind[i].size();j++)
      |                     ~^~~~~~~~~~~~~~
rect.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         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: 28 / 28