Submission #1069482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069482		12345678	Rectangles (IOI19_rect)	C++17	100 / 100	1800 ms	808248 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=2505;

int jr[nx][nx], jdn[nx][nx];
vector<pair<int, int>> dpr[nx][nx], dpdn[nx][nx];
stack<int> s;

struct fenwick
{
    int d[nx];
    void add(int i, int vl)
    {
        while (i<nx) d[i]+=vl, i+=(i&-i);
    }
    int query(int i)
    {
        int tmp=0;
        while (i>0) tmp+=d[i], i-=(i&-i);
        return tmp;
    }
} f;

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n=a.size(), m=a[0].size();
	long long res=0, res2=0;
    for (int i=0; i<n; i++) for (int j=0; j<m; j++) jdn[i][j]=jr[i][j]=-1, dpr[i][j].clear(), dpdn[i][j].clear();
    for (int i=n-1; i>=0; i--)
    {
        while (!s.empty()) s.pop();
        for (int j=m-1; j>=0; j--)
        {
            while (!s.empty()&&a[i][j]>=a[i][s.top()]) s.pop();
            if (!s.empty()) jr[i][j]=s.top();
            s.push(j);
            int curj=j+1;
            while (curj<m&&a[i][j]>a[i][curj])
            {
                curj=jr[i][curj];
                if (curj==-1) break;
                auto itr=lower_bound(dpr[i+1][j].begin(), dpr[i+1][j].end(), make_pair(curj, 0));
                if (itr!=dpr[i+1][j].end()&&itr->first==curj) dpr[i][j].push_back({curj, itr->second});
                else dpr[i][j].push_back({curj, i+1});
            }
        }
    }
    for (int j=m-1; j>=0; j--)
    {
        while (!s.empty()) s.pop();
        for (int i=n-1; i>=0; i--)
        {
            while (!s.empty()&&a[i][j]>=a[s.top()][j]) s.pop();
            if (!s.empty()) jdn[i][j]=s.top();
            s.push(i);
            int curi=i+1;
            while (curi<n&&a[i][j]>a[curi][j])
            {
                curi=jdn[curi][j];
                if (curi==-1) break;
                //if (i==0&&j==1) cout<<"jump "<<curi<<'\n';
                auto itr=lower_bound(dpdn[i][j+1].begin(), dpdn[i][j+1].end(), make_pair(curi, 0));
                //if (i==0&&j==1) cout<<"itr "<<itr->first<<' '<<itr->second<<'\n'; 
                if (itr!=dpdn[i][j+1].end()&&itr->first==curi) dpdn[i][j].push_back({curi, itr->second});
                else dpdn[i][j].push_back({curi, j+1});
            }
        }
    }
    for (int i=0; i<n-1; i++)
    {
        for (int j=0; j<m-1; j++)
        {
            sort(dpr[i+1][j].begin(), dpr[i+1][j].end(), [](pair<int, int> a, pair<int, int> b){return a.second>b.second;});
            sort(dpdn[i][j+1].begin(), dpdn[i][j+1].end());
            reverse(dpdn[i][j+1].begin(), dpdn[i][j+1].end());
            int idx=0;
            for (auto x:dpdn[i][j+1])
            {
                while (idx<dpr[i+1][j].size()&&dpr[i+1][j][idx].second>=x.first) f.add(dpr[i+1][j][idx].first, 1), idx++;
                res+=f.query(x.second);
            }
            while (--idx>=0) f.add(dpr[i+1][j][idx].first, -1);
        }
    }
	return res;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                 while (idx<dpr[i+1][j].size()&&dpr[i+1][j][idx].second>=x.first) f.add(dpr[i+1][j][idx].first, 1), idx++;
      |                        ~~~^~~~~~~~~~~~~~~~~~~
rect.cpp:29:19: warning: unused variable 'res2' [-Wunused-variable]
   29 |  long long res=0, res2=0;
      |                   ^~~~

• 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