Submission #294311

#	Time	Username	Problem	Language	Result	Execution time	Memory
294311		Pajaraja	Rectangles (IOI19_rect)	C++17	23 / 100	2471 ms	882112 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define MAXN 2507
using namespace std;
set<int> sv[MAXN][MAXN],sh[MAXN][MAXN];
vector<int> qx,qy,ql,qt,ind[MAXN];
int bit[MAXN][MAXN];
void upd(int k,int u,int v)
{
    while(u<MAXN)
    {
        bit[k][u]+=v;
        u+=u&(-u);
    }
}
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)
{
    if(ql[a]!=ql[b]) return ql[a]<ql[b];
    if(qt[a]!=qt[b]) return qt[a]<qt[b];
    return false;
}
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++)
    {
        stack<int> st;
        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) sv[i][j-1].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) sv[i][st.top()-1].insert(j+1);
            st.push(j);
        }
    }
    for(int i=1;i<m-1;i++)
    {
        stack<int> st;
        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) sh[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) sh[st.top()-1][i].insert(j+1);
            st.push(j);
        }
    }
    for(int i=1;i<n-1;i++)
    {
        for(int j=1;j<m;j++)
        {
            for(set<int>::iterator it=sh[i][j].begin();it!=sh[i][j].end();it++)
            {
                for(int k=j+1;k<m;k++)
                {
                    if(sh[i][k].find(*it)==sh[i][k].end()) {qx.push_back(j); qy.push_back(k-1); qt.push_back(2); ql.push_back(*it); ind[i].push_back(qx.size()-1); break;}
                    else sh[i][k].erase(*it);
                }
            }

        }
    }
    for(int j=1;j<m-1;j++)
    {
        for(int i=1;i<n;i++)
        {
            for(set<int>::iterator it=sv[i][j].begin();it!=sv[i][j].end();it++)
            {
                for(int k=i;k<n-1;k++)
                {
                    if(sv[k][j].find(*it)==sv[k][j].end()) break;
                    else {if(k!=i) sv[k][j].erase(j); qx.push_back(*it); qy.push_back(j); qt.push_back(1); ql.push_back(i); ind[k].push_back(qx.size()-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(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);
    }
	return sol;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int j=0;j<ind[i].size();j++)
      |                     ~^~~~~~~~~~~~~~
rect.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         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: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28