Submission #473319

#	Time	Username	Problem	Language	Result	Execution time	Memory
473319		blue	Rectangles (IOI19_rect)	C++17	72 / 100	3148 ms	1048580 KiB

rect

#include "rect.h"
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <iostream>
using namespace std;

/*
Red = |    |
      |    |


Green = ----

        ----

*/
vector<int> green_R2;
vector<int> green_C2;
vector<int> red_R2;
vector<int> red_C2;

int R, G;

long long count_rectangles(vector< vector<int> > A)
{
    int N = (int)A.size();
    int M = (int)A[0].size();













    vector< vector< vector<int> > > red_occ(M, vector< vector<int> >(M));
    for(int i = 0; i < N; i++)
    {
        vector<int> st;
        st.push_back(-1);
        for(int j = 0; j < M; j++)
        {
            // if(i == 1)
            // {
            //     // cerr << "j = " << j << '\n';
            //     // cerr << "st = ";
            //     // for(int h: st) cerr << h << ' ';
            //     // cerr << '\n';
            // }
            while(st.back() != -1 && A[i][st.back()] < A[i][j])
            {
                if(st.back() != j-1)
                {
                    // if(i == 1) cerr << "red " << st.back() + 1 << ' ' << j-1 << '\n';
                    red_occ[ st.back() + 1 ][j - 1].push_back(i);
                }
                st.pop_back();
            }

            if(st.back() != j-1 && st.back() != -1)
            {
                // if(i == 1) cerr << "red " << st.back() + 1 << ' ' << j-1 << '\n';
                red_occ[ st.back() + 1 ][j - 1].push_back(i);
            }
            while(st.back() != -1 && A[i][st.back()] == A[i][j])
                st.pop_back();
            st.push_back(j);
        }
    }

    // cerr << "Red\n";
    vector<int> red_r1, red_r2, red_c1, red_c2;
    for(int c1 = 0; c1 < M; c1++)
    {
        for(int c2 = c1; c2 < M; c2++)
        {
            if(red_occ[c1][c2].empty()) continue;

            vector<int> B, E;
            B.push_back(red_occ[c1][c2][0]);

            for(int x = 0; x+1 < (int)red_occ[c1][c2].size(); x++)
            {
                if(red_occ[c1][c2][x] + 1 != red_occ[c1][c2][x+1])
                {
                    E.push_back(red_occ[c1][c2][x]);
                    B.push_back(red_occ[c1][c2][x+1]);
                }
            }

            E.push_back(red_occ[c1][c2].back());

            for(int q = 0; q < (int)B.size(); q++)
            {
                // cerr << B[q] << ' ' << c1 << ' ' << E[q] << ' ' << c2 << '\n';
                red_r1.push_back(B[q]);
                red_r2.push_back(E[q]);
                red_c1.push_back(c1);
                red_c2.push_back(c2);
            }
        }
    }
    red_occ.clear();

    vector<int> red_opp_r[N][M], red_opp_c[N][M];
    for(int q = 0; q < (int)red_r1.size(); q++)
    {
        for(int r = red_r1[q]; r <= red_r2[q]; r++)
        {
            red_opp_r[r][red_c1[q]].push_back(red_r2[q]);
            red_opp_c[r][red_c1[q]].push_back(red_c2[q]);
        }
    }

    red_r1.clear();
    red_r2.clear();
    red_c1.clear();
    red_c2.clear();


























    vector<int> green_occ[N][N];  //CHECK THAT EVERYTHING IS SYMMETRIC!!!!!
    for(int j = 0; j < M; j++)
    {
        // cerr << "col = " << j << '\n';
        vector<int> st;
        st.push_back(-1);
        for(int i = 0; i < N; i++)
        {
            while(st.back() != -1 && A[st.back()][j] < A[i][j])
            {
                if(st.back() != i-1)
                {
                    // cerr << st.back() + 1 << ' ' << i-1 << '\n';
                    green_occ[st.back() + 1][i - 1].push_back(j);
                }
                st.pop_back();
            }

            if(st.back() != i-1 && st.back() != -1)
            {
                // cerr << st.back() + 1 << ' ' << i-1 << '\n';
                green_occ[st.back() + 1][i - 1].push_back(j);
            }
            while(st.back() != -1 && A[st.back()][j] == A[i][j])
                st.pop_back();
            st.push_back(i);
        }
    }
    // cerr << "check\n";
    // cerr << "Green\n";

    vector<int> green_r1, green_r2, green_c1, green_c2;
    for(int r1 = 0; r1 < N; r1++)
    {
        for(int r2 = r1; r2 < N; r2++)
        {
            if(green_occ[r1][r2].empty()) continue;
            // cer

            vector<int> B, E;

            B.push_back(green_occ[r1][r2][0]);

            for(int x = 0; x+1 < (int)green_occ[r1][r2].size(); x++)
            {
                if(green_occ[r1][r2][x] + 1 != green_occ[r1][r2][x+1])
                {
                    E.push_back(green_occ[r1][r2][x]);
                    B.push_back(green_occ[r1][r2][x+1]);
                }
            }

            E.push_back(green_occ[r1][r2].back());

            for(int q = 0; q < (int)B.size(); q++)
            {
                green_r1.push_back(r1);
                green_r2.push_back(r2);
                green_c1.push_back(B[q]);
                green_c2.push_back(E[q]);

                // cerr << r1 << ' ' << B[q] << ' ' << r2 << ' ' << E[q] << '\n';
            }
        }
    }
    vector<int> green_opp_r[N][M], green_opp_c[N][M];
    for(int q = 0; q < (int)green_r1.size(); q++)
    {
        for(int c = green_c1[q]; c <= green_c2[q]; c++)
        {
            green_opp_r[green_r1[q]][c].push_back(green_r2[q]);
            green_opp_c[green_r1[q]][c].push_back(green_c2[q]);
        }
    }
    green_r1.clear();
    green_r2.clear();
    green_c1.clear();
    green_c2.clear();


    for(int i = 0; i < N; i++)
        A[i].clear();
    A.clear();













    int MX = 4'096;
    vector<int> BIT(1+MX, 0);

    long long res = 0;

    for(int r1 = 0; r1 < N; r1++)
    {
        for(int c1 = 0; c1 < M; c1++)
        {
            long long res1 = res;

            green_R2 = green_opp_r[r1][c1];
            green_C2 = green_opp_c[r1][c1];

            red_R2 = red_opp_r[r1][c1];
            red_C2 = red_opp_c[r1][c1];

            vector<int> I((int)green_R2.size() + (int)red_R2.size());
            for(int i = 0; i < (int)I.size(); i++)
                I[i] = i;

            G = (int)green_R2.size();
            R = (int)red_R2.size();
            //sweep line by row
            //fenwick tree by column
            //green comes first
            sort(I.begin(), I.end(), [] (int p, int q)
            {
                int r_p, c_p, r_q, c_q;

                if(p < G)
                {
                    r_p = green_R2[p];
                    c_p = green_C2[p];
                }
                else
                {
                    r_p = red_R2[p - G];
                    c_p = red_C2[p - G];
                }

                if(q < G)
                {
                    r_q = green_R2[q];
                    c_q = green_C2[q];
                }
                else
                {
                    r_q = red_R2[q - G];
                    c_q = red_C2[q - G];
                }

                if(r_p != r_q) return r_p < r_q;
                else return p < q;
            });

            for(int i:I)
            {
                if(i < G)
                    for(int b = green_C2[i]+1; b <= MX; b += b&-b)
                        BIT[b]++;
                else
                {
                    for(int b = MX; b >= 1; b -= b&-b)
                        res += BIT[b];
                    for(int b = red_C2[i - G]+1 - 1; b >= 1; b -= b&-b)
                        res -= BIT[b];
                }
            }

            for(int i:I)
            {
                if(i < G)
                    for(int b = green_C2[i]+1; b <= MX; b += b&-b)
                         BIT[b] = 0;
            }

            // if(res != res1)
            // {
            //     cout << "top left = " << r1 << ' ' << c1 << ", diff = " << res - res1 << '\n';
            // }
        }
    }

    return res;
}

Compilation message (stderr)

rect.cpp: In lambda function:
rect.cpp:277:26: warning: variable 'c_p' set but not used [-Wunused-but-set-variable]
  277 |                 int r_p, c_p, r_q, c_q;
      |                          ^~~
rect.cpp:277:36: warning: variable 'c_q' set but not used [-Wunused-but-set-variable]
  277 |                 int r_p, c_p, r_q, c_q;
      |                                    ^~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:258:23: warning: unused variable 'res1' [-Wunused-variable]
  258 |             long long res1 = res;
      |                       ^~~~

• 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