Submission #473415

#	Time	Username	Problem	Language	Result	Execution time	Memory
473415		blue	Rectangles (IOI19_rect)	C++17	100 / 100	4425 ms	968660 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;

int R, G;

const int MD = 3'000;

vector<int> red_opp[2500][2500];
vector<int> green_opp[2500][2500];
int r1, c1, r2, c2;

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++)
        {
            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;

    // vector<int> red_opp_r[N][M], red_opp_c[N][M];
    for(c1 = 0; c1 < M; c1++)
    {
        for(c2 = c1; c2 < M; c2++)
        {
            if(red_occ[c1][c2].empty()) continue;

            // vector<int> B, E;
            // B.push_back(red_occ[c1][c2][0]);
            int B1 = 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])
                {
                    int E1 = red_occ[c1][c2][x];

                    for(int r = B1; r <= E1; r++)
                    {
                        // red_opp_r[r][c1].push_back(E1);
                        // red_opp_c[r][c1].push_back(c2);
                        red_opp[r][c1].push_back(MD*E1+c2);
                    }


                    B1 = 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());
            int E1 = red_occ[c1][c2].back();
            for(int r = B1; r <= E1; r++)
            {
                // red_opp_r[r][c1].push_back(E1);
                // red_opp_c[r][c1].push_back(c2);
                red_opp[r][c1].push_back(MD*E1 + c2);
            }
        }
    }
    red_occ.clear();


























    vector< vector< vector<int> > > green_occ(N, vector< vector<int> >(N));  //CHECK THAT EVERYTHING IS SYMMETRIC!!!!!
    for(int j = 0; j < M; j++)
    {
        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)
                {
                    green_occ[st.back() + 1][i - 1].push_back(j);
                }
                st.pop_back();
            }

            if(st.back() != i-1 && st.back() != -1)
            {
                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);
        }
    }

    // vector<int> green_opp_r[N][M], green_opp_c[N][M];
    for(r1 = 0; r1 < N; r1++)
    {
        for(r2 = r1; r2 < N; r2++)
        {
            if(green_occ[r1][r2].empty()) continue;
            // cer

            // vector<int> B, E;

            int B1 = green_occ[r1][r2][0];

            // 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])
                {
                    int E1 = green_occ[r1][r2][x];

                    for(int c = B1; c <= E1; c++)
                    {
                        // green_opp_r[r1][c].push_back(r2);
                        // green_opp_c[r1][c].push_back(E1);
                        green_opp[r1][c].push_back(MD*r2+E1);
                    }

                    B1 = green_occ[r1][r2][x+1];

                }
            }
            int E1 = green_occ[r1][r2].back();
            for(int c = B1; c <= E1; c++)
            {
                // green_opp_r[r1][c].push_back(r2);
                // green_opp_c[r1][c].push_back(E1);
                green_opp[r1][c].push_back(MD*r2+E1);
        }
    }
    }
    green_occ.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(r1 = 0; r1 < N; r1++)
    {
        for(c1 = 0; c1 < M; c1++)
        {
            // cerr << r1 << ' ' << c1 << '\n';
            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];
            // cerr << "check2\n";

            vector<int> I((int)(green_opp[r1][c1]).size() + (int)(red_opp[r1][c1]).size());
            for(int i = 0; i < (int)I.size(); i++)
                I[i] = i;

            G = (int)(green_opp[r1][c1]).size();
            R = (int)(red_opp[r1][c1]).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_opp[r1][c1][p] / MD;
                    c_p = green_opp[r1][c1][p] % MD;
                }
                else
                {
                    // r_p = (*red_R2)[p - G];
                    // c_p = (*red_C2)[p - G];
                    r_p = red_opp[r1][c1][p - G] / MD;
                    c_p = red_opp[r1][c1][p - G] % MD;
                }

                if(q < G)
                {
                    r_q = green_opp[r1][c1][q] / MD;
                    c_q = green_opp[r1][c1][q] % MD;
                }
                else
                {
                    // r_q = (*red_R2)[q - G];
                    // c_q = (*red_C2)[q - G];
                    r_q = red_opp[r1][c1][q - G] / MD;
                    c_q = red_opp[r1][c1][q - G] % MD;
                }

                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_opp[r1][c1][i]%MD)+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_opp[r1][c1][i - G]%MD)+1 - 1; b >= 1; b -= b&-b)
                        res -= BIT[b];
                }
            }

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

        // cerr << "check\n";

    return res;

}

Compilation message (stderr)

rect.cpp: In lambda function:
rect.cpp:261:26: warning: variable 'c_p' set but not used [-Wunused-but-set-variable]
  261 |                 int r_p, c_p, r_q, c_q;
      |                          ^~~
rect.cpp:261:36: warning: variable 'c_q' set but not used [-Wunused-but-set-variable]
  261 |                 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:241:23: warning: unused variable 'res1' [-Wunused-variable]
  241 |             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: 28 / 28