Submission #1190141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190141		alexdd	Rectangles (IOI19_rect)	C++20	100 / 100	2162 ms	889192 KiB

rect

#pragma GCC optimize("O3,unroll-loops")
#include "rect.h"
#include<iostream>
#include<cassert>
#include<algorithm>
using namespace std;
int n,m;
vector<pair<int,int>> get_bune(const vector<int>&v)
{
    vector<pair<int,int>> bune;
    vector<int> dq;
    for(int i=0;i<v.size();i++)
    {
        while(!dq.empty() && v[i] > v[dq.back()])
        {
            if(dq.back()+1 <= i-1)
                bune.push_back({dq.back()+1,i-1});
            dq.pop_back();
        }
        if(!dq.empty() && dq.back()+1 <= i-1)
            bune.push_back({dq.back()+1,i-1});
        if(!dq.empty() && v[dq.back()] == v[i])
            dq.pop_back();
        dq.push_back(i);
    }
    return bune;
}
vector<pair<int,int>> bune_pe_rand[2505];
vector<int> coloane_bune[2505][2505];
vector<int> randuri_bune[2505][2505],primu[2505][2505];
int poz_rbune[2505][2505];

int aib[2505][10005];
int sizaib[2505];
int cntscos[2505][2505];
void baga(int x, int y)
{
    x++;
    y++;

    int aux=0;
    for(int i=x;i>0;i-=(i&(-i)))
    {
        aib[i][sizaib[i]++] = y;
    }
}
void init()
{
    for(int i=1;i<=m;i++)
    {
        sort(aib[i],aib[i]+sizaib[i]);
        reverse(aib[i],aib[i]+sizaib[i]);
    }
}
void scoate(int x, int y)//------------------------------------------------------
{
    x++;
    y++;

    for(int i=x;i>0;i-=(i&(-i)))
        cntscos[i][y]++;
}
void scoate_tot()
{
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<sizaib[i];j++)
            cntscos[i][aib[i][j]]=0;
        sizaib[i]=0;
    }
}
int debagat[1000000],cntdeb;
int qry(int x, int y)
{
    x++;
    y++;

    int aux=0;
    for(int i=x;i<=m;i+=(i&(-i)))
    {
        if(sizaib[i]==0 || aib[i][sizaib[i]-1] > y)continue;

        cntdeb=0;
        for(int j=sizaib[i]-1;j>=0 && aib[i][j]<=y;j--)
        {
            if(cntscos[i][aib[i][j]] > 0)
            {
                cntscos[i][aib[i][j]]--;
                sizaib[i]--;
            }
            else
            {
                debagat[cntdeb++] = aib[i][j];
                aux++;
            }
        }
        for(int j=0;j<cntdeb;j++)
            aib[i][sizaib[i]-1-j] = debagat[j];
    }
    return aux;
}

vector<pair<int,int>> scoase[2505];

long long count_rectangles(std::vector<std::vector<int>> a)
{
    n = a.size();
    m = a[0].size();
    long long rez=0;
    for(int i=1;i+1<a.size();i++)
    {
        bune_pe_rand[i] = get_bune(a[i]);
        for(auto [x,y]:bune_pe_rand[i])
            randuri_bune[x][y].push_back(i);
    }
    for(int x=1;x+1<m;x++)
    {
        for(int y=x;y+1<m;y++)
        {
            if(randuri_bune[x][y].empty())
                continue;
            primu[x][y].resize(randuri_bune[x][y].size() + 2);
            int ult = a.size();
            if(randuri_bune[x][y].back() != (int)a.size() - 2)
                ult = randuri_bune[x][y].back() + 1;
            primu[x][y][randuri_bune[x][y].size()] = ult;
            for(int i=randuri_bune[x][y].size()-1;i>0;i--)
            {
                if(randuri_bune[x][y][i] != randuri_bune[x][y][i-1] + 1)
                    ult = randuri_bune[x][y][i-1] + 1;
                primu[x][y][i] = ult;
            }
        }
    }
    for(int i=1;i+1<m;i++)
    {
        vector<int> aux;
        for(int j=0;j<a.size();j++)
            aux.push_back(a[j][i]);
        vector<pair<int,int>> bune = get_bune(aux);
        for(auto [x,y]:bune)
            coloane_bune[x][y].push_back(i);
    }
    for(int sus=1;sus+1<a.size();sus++)
    {
        for(int jos=sus;jos<=a.size();jos++)
            scoase[jos].clear();
        for(auto [x,y]:bune_pe_rand[sus])
        {
            baga(x,y);
            while(randuri_bune[x][y][poz_rbune[x][y]] < sus)
                poz_rbune[x][y]++;
            scoase[primu[x][y][poz_rbune[x][y]+1]].push_back({x,y});
        }
        init();
        for(int jos=sus;jos+1<a.size();jos++)
        {
            //for(int i=0;i<scoase[jos].size();i++) upd(scoase[jos][i].first,scoase[jos][i].second,-1);
            for(auto [x,y]:scoase[jos]) scoate(x,y);
            //for(pair<int,int> x:scoase[jos]) upd(x.first,x.second,-1);


            if(!coloane_bune[sus][jos].empty())
            {
                int ult=0;
                for(int i=0;i+1<coloane_bune[sus][jos].size();i++)
                {
                    if(coloane_bune[sus][jos][i] + 1 != coloane_bune[sus][jos][i+1])
                    {
                        rez += qry(coloane_bune[sus][jos][ult],coloane_bune[sus][jos][i]);
                        ult = i+1;
                    }
                }
                rez += qry(coloane_bune[sus][jos][ult],coloane_bune[sus][jos][coloane_bune[sus][jos].size() - 1]);
            }

        }
        scoate_tot();
    }
    assert(rez <= 4*n*m);
    return rez;
}
/*

ne fixam linia de sus
apoi mergem cu linia de jos in jos, o sa avem la inceput O(N) perechi de coloane candidate
cand adaugam o linie in jos o sa dezactivam niste perechi de coloane

trebuie sa verificam pt fiecare (sus,jos) care coloane sunt bune

asta o sa fie O(N^2), pt ca fiecare coloana o sa apara in O(N) (sus,jos)-uri

facem un dsu in care tinem si candidatii de perechi de coloane si cam asta e tot sper

*/

• 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