Submission #1064900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064900		jerzyk	Rectangles (IOI19_rect)	C++17	100 / 100	4712 ms	722336 KiB

rect

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 2500 + 7;
int tab[N][N];
vector<int> intr[N][N];
vector<pair<int, int>> que[N][N];
bool czy[N];
long long answer = 0;



void CntR(int n, int m)
{
    for(int i = 1; i <= n; ++i)
    {
        vector<pair<int, int>> kol;
        for(int j = m; j >= 1; --j)
        {
            while((int)kol.size() > 0 && kol.back().st <= tab[i][j])
                kol.pop_back();
            int xd = tab[i][j];
            //cerr << "R: " << i << " " << j << "\n";
            for(int k = kol.size() - 1; k >= 0 && tab[i][j - 1] > xd; --k)
            {
                intr[i][j].pb(kol[k].nd - 1);
                //cerr << kol[k].nd - 1 << " ";
                xd = max(xd, kol[k].st);
            }
            //cout << "\n";
            kol.pb(make_pair(tab[i][j], j));
        }
    }
    for(int j = 1; j <= m; ++j)
    {
        vector<pair<int, int>> akt;
        for(int i = j; i <= m; ++i)
            akt.pb(make_pair(i, 1));
        for(int i = 1; i <= n; ++i)
        {
            vector<pair<int, int>> nxt;
            int k = 0;
            //cerr << "DP: " << i << " " << j << "\n";
            for(int l = 0; l < (int)intr[i][j].size(); ++l)
            {
                while(k < (int)akt.size() && akt[k].st < intr[i][j][l])
                    ++k;
                if(k < (int)akt.size() && akt[k].st == intr[i][j][l])
                {
                    nxt.pb(akt[k]);
                    ++k;
                }else
                    nxt.pb(make_pair(intr[i][j][l], i));

                que[i][intr[i][j][l]].pb(make_pair(j, i - nxt.back().nd + 1));
                //cerr << nxt.back().st << " " << nxt.back().nd << "\n";
            }
            akt = nxt;
            intr[i][j].clear();
        }
    }
}

void CntL(int n, int m)
{
    for(int j = 1; j <= m; ++j)
    {
        vector<pair<int, int>> kol;
        for(int i = 1; i <= n; ++i)
        {
            while((int)kol.size() > 0 && kol.back().st <= tab[i][j])
                kol.pop_back();
            int xd = tab[i][j];
            //cerr << "U: " << i << " " << j << "\n";
            for(int k = kol.size() - 1; k >= 0 && tab[i + 1][j] > xd; --k)
            {
                intr[i][j].pb(kol[k].nd + 1);
                //cerr << kol[k].nd + 1 << "\n";
                xd = max(xd, kol[k].st);
            }
            sort(intr[i][j].begin(), intr[i][j].end());
            kol.pb(make_pair(tab[i][j], i));
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        vector<pair<int, int>> akt;
        for(int j = i; j <= n; ++j)
            akt.pb(make_pair(j, 1));
        for(int j = 1; j <= m; ++j)
        {
            vector<pair<int, int>> nxt;
            int k = 0;
            //cerr << "DP: " << i << " " <<  j << "\n";
            for(int l = 0; l < (int)intr[i][j].size(); ++l)
            {
                while(k < (int)akt.size() && akt[k].st < intr[i][j][l])
                    ++k;
                if(k < (int)akt.size() && akt[k].st == intr[i][j][l])
                {
                    nxt.pb(make_pair(akt[k].nd, akt[k].st));
                    ++k;
                }else
                    nxt.pb(make_pair(j, intr[i][j][l]));
                //cerr << nxt.back().nd << " " << nxt.back().st << "\n";
            }
            akt = nxt;
            sort(akt.begin(), akt.end());
            int lim = akt.size();
            //cout << "QUE: " << i << " " << j << "\n";
            for(int l = 0; l < (int)que[i][j].size(); ++l)
            {
                //cout << que[i][j][l].st << " " << que[i][j][l].nd << "\n";
                for(int r = 0; r < lim; ++r)
                    if(akt[r].st <= que[i][j][l].st && i - akt[r].nd + 1 <= que[i][j][l].nd)
                         ++answer;
            }

            for(int l = 0; l < (int)akt.size(); ++l)
                swap(akt[l].st, akt[l].nd);
            sort(akt.begin(), akt.end());
            intr[i][j].clear();
        }
    }
}

long long count_rectangles(vector<vector<int>> xd)
{
    int n = xd.size(), m = xd[0].size();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            tab[i][j] = xd[i - 1][j - 1];
    CntR(n, m);
    CntL(n, m);
    return answer;
}

• 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