Submission #294362

#	Time	Username	Problem	Language	Result	Execution time	Memory
294362		Pajaraja	Rectangles (IOI19_rect)	C++17	72 / 100	5124 ms	681740 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define MAXN 2507
using namespace std;
set<int> s[MAXN][MAXN];
vector<int> ind[MAXN];
int qx[MAXN*MAXN],qy[MAXN*MAXN],ql[MAXN*MAXN],qt[MAXN*MAXN],cnt;
stack<int> st;
int bit[MAXN][MAXN];
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 2*ql[a]+qt[a]<2*ql[b]+qt[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].insert(st.top()+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) s[st.top()-1][i].insert(j+1);
            st.push(j);
        }
        while(!st.empty()) st.pop();
    }
    for(int j=1;j<m-1;j++)
    {
        for(int i=1;i<n;i++)
        {
            for(set<int>::iterator it=s[j][i].begin();it!=s[j][i].end();it++)
            {
                for(int k=i;k<n-1;k++)
                {
                    if(s[j][k].find(*it)==s[j][k].end()) break;
                    else {if(k!=i) s[j][k].erase(*it); qx[cnt]=*it; qy[cnt]=j; qt[cnt]=1; ql[cnt]=i; ind[k].push_back(cnt++);}
                }
            }
            s[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].insert(st.top()+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) s[st.top()-1][i].insert(j+1);
            st.push(j);
        }
        while(!st.empty()) st.pop();
    }
    for(int i=1;i<n-1;i++)
    {
        for(int j=1;j<m;j++)
        {
            for(set<int>::iterator it=s[i][j].begin();it!=s[i][j].end();it++)
            {
                for(int k=j+1;k<m;k++)
                {
                    if(s[i][k].find(*it)==s[i][k].end()) {qx[cnt]=j; qy[cnt]=k-1; qt[cnt]=2; ql[cnt]=*it; ind[i].push_back(cnt++); break;}
                    else s[i][k].erase(*it);
                }
            }
        }
    }
    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(qt[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(qt[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:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int j=0;j<ind[i].size();j++)
      |                     ~^~~~~~~~~~~~~~
rect.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int j=0;j<ind[i].size();j++) if(qt[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