Submission #473428

#	Time	Username	Problem	Language	Result	Execution time	Memory
473428		blue	Rectangles (IOI19_rect)	C++17	100 / 100	4536 ms	933884 KiB

rect

#include "rect.h"
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <iostream>
using namespace std;
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)
                    red_occ[ st.back() + 1 ][j - 1].push_back(i);
                st.pop_back();
            }
            if(st.back() != j-1 && st.back() != -1) {
                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);
        }
    }
    for(c1 = 0; c1 < M; c1++) {
        for(c2 = c1; c2 < M; c2++) {
            if(red_occ[c1][c2].empty()) continue;
            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][c1].push_back(MD*E1+c2);
                    B1 = red_occ[c1][c2][x+1];
                }
            }
            int E1 = red_occ[c1][c2].back();
            for(int r = B1; r <= E1; r++)
                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);
        }
    }
    for(r1 = 0; r1 < N; r1++){
        for(r2 = r1; r2 < N; r2++){
            if(green_occ[r1][r2].empty()) continue;
            int B1 = 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[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[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++) {
            long long res1 = res;
            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();
            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_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_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;
            }
        }
    }
    return res;
}

Compilation message (stderr)

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