oj.uz

답안 #473415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
473415 2021-09-15T13:23:27 Z blue Rectangles (IOI19_rect) C++17
100 / 100
 4425 ms 968660 KB 
#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

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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 293724 KB Output is correct
2 Correct 159 ms 293800 KB Output is correct
3 Correct 159 ms 293832 KB Output is correct
4 Correct 160 ms 293832 KB Output is correct
5 Correct 168 ms 293828 KB Output is correct
6 Correct 152 ms 293816 KB Output is correct
7 Correct 161 ms 293840 KB Output is correct
8 Correct 189 ms 293764 KB Output is correct
9 Correct 158 ms 293828 KB Output is correct
10 Correct 188 ms 293864 KB Output is correct
11 Correct 171 ms 293868 KB Output is correct
12 Correct 153 ms 293760 KB Output is correct
13 Correct 158 ms 293764 KB Output is correct
14 Correct 157 ms 293728 KB Output is correct
15 Correct 246 ms 293764 KB Output is correct
16 Correct 170 ms 293712 KB Output is correct
17 Correct 191 ms 293804 KB Output is correct
18 Correct 170 ms 293796 KB Output is correct
19 Correct 178 ms 293756 KB Output is correct
20 Correct 178 ms 293828 KB Output is correct
21 Correct 172 ms 293808 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 293724 KB Output is correct
2 Correct 159 ms 293800 KB Output is correct
3 Correct 159 ms 293832 KB Output is correct
4 Correct 160 ms 293832 KB Output is correct
5 Correct 168 ms 293828 KB Output is correct
6 Correct 152 ms 293816 KB Output is correct
7 Correct 161 ms 293840 KB Output is correct
8 Correct 189 ms 293764 KB Output is correct
9 Correct 158 ms 293828 KB Output is correct
10 Correct 188 ms 293864 KB Output is correct
11 Correct 171 ms 293868 KB Output is correct
12 Correct 153 ms 293760 KB Output is correct
13 Correct 158 ms 293764 KB Output is correct
14 Correct 157 ms 293728 KB Output is correct
15 Correct 246 ms 293764 KB Output is correct
16 Correct 170 ms 293712 KB Output is correct
17 Correct 191 ms 293804 KB Output is correct
18 Correct 170 ms 293796 KB Output is correct
19 Correct 178 ms 293756 KB Output is correct
20 Correct 178 ms 293828 KB Output is correct
21 Correct 172 ms 293808 KB Output is correct
22 Correct 171 ms 294456 KB Output is correct
23 Correct 162 ms 294484 KB Output is correct
24 Correct 163 ms 294428 KB Output is correct
25 Correct 176 ms 294176 KB Output is correct
26 Correct 164 ms 294268 KB Output is correct
27 Correct 163 ms 294260 KB Output is correct
28 Correct 165 ms 294212 KB Output is correct
29 Correct 163 ms 294064 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 293724 KB Output is correct
2 Correct 159 ms 293800 KB Output is correct
3 Correct 159 ms 293832 KB Output is correct
4 Correct 160 ms 293832 KB Output is correct
5 Correct 168 ms 293828 KB Output is correct
6 Correct 152 ms 293816 KB Output is correct
7 Correct 161 ms 293840 KB Output is correct
8 Correct 189 ms 293764 KB Output is correct
9 Correct 158 ms 293828 KB Output is correct
10 Correct 188 ms 293864 KB Output is correct
11 Correct 171 ms 293868 KB Output is correct
12 Correct 153 ms 293760 KB Output is correct
13 Correct 158 ms 293764 KB Output is correct
14 Correct 157 ms 293728 KB Output is correct
15 Correct 246 ms 293764 KB Output is correct
16 Correct 170 ms 293712 KB Output is correct
17 Correct 171 ms 294456 KB Output is correct
18 Correct 162 ms 294484 KB Output is correct
19 Correct 163 ms 294428 KB Output is correct
20 Correct 176 ms 294176 KB Output is correct
21 Correct 164 ms 294268 KB Output is correct
22 Correct 163 ms 294260 KB Output is correct
23 Correct 165 ms 294212 KB Output is correct
24 Correct 163 ms 294064 KB Output is correct
25 Correct 191 ms 293804 KB Output is correct
26 Correct 170 ms 293796 KB Output is correct
27 Correct 178 ms 293756 KB Output is correct
28 Correct 178 ms 293828 KB Output is correct
29 Correct 172 ms 293808 KB Output is correct
30 Correct 168 ms 297948 KB Output is correct
31 Correct 180 ms 297980 KB Output is correct
32 Correct 176 ms 298144 KB Output is correct
33 Correct 171 ms 295996 KB Output is correct
34 Correct 183 ms 296796 KB Output is correct
35 Correct 179 ms 296880 KB Output is correct
36 Correct 180 ms 296900 KB Output is correct
37 Correct 190 ms 296808 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 293724 KB Output is correct
2 Correct 159 ms 293800 KB Output is correct
3 Correct 159 ms 293832 KB Output is correct
4 Correct 160 ms 293832 KB Output is correct
5 Correct 168 ms 293828 KB Output is correct
6 Correct 152 ms 293816 KB Output is correct
7 Correct 161 ms 293840 KB Output is correct
8 Correct 189 ms 293764 KB Output is correct
9 Correct 158 ms 293828 KB Output is correct
10 Correct 188 ms 293864 KB Output is correct
11 Correct 171 ms 293868 KB Output is correct
12 Correct 153 ms 293760 KB Output is correct
13 Correct 158 ms 293764 KB Output is correct
14 Correct 157 ms 293728 KB Output is correct
15 Correct 246 ms 293764 KB Output is correct
16 Correct 170 ms 293712 KB Output is correct
17 Correct 171 ms 294456 KB Output is correct
18 Correct 162 ms 294484 KB Output is correct
19 Correct 163 ms 294428 KB Output is correct
20 Correct 176 ms 294176 KB Output is correct
21 Correct 164 ms 294268 KB Output is correct
22 Correct 163 ms 294260 KB Output is correct
23 Correct 165 ms 294212 KB Output is correct
24 Correct 163 ms 294064 KB Output is correct
25 Correct 168 ms 297948 KB Output is correct
26 Correct 180 ms 297980 KB Output is correct
27 Correct 176 ms 298144 KB Output is correct
28 Correct 171 ms 295996 KB Output is correct
29 Correct 183 ms 296796 KB Output is correct
30 Correct 179 ms 296880 KB Output is correct
31 Correct 180 ms 296900 KB Output is correct
32 Correct 190 ms 296808 KB Output is correct
33 Correct 191 ms 293804 KB Output is correct
34 Correct 170 ms 293796 KB Output is correct
35 Correct 178 ms 293756 KB Output is correct
36 Correct 178 ms 293828 KB Output is correct
37 Correct 172 ms 293808 KB Output is correct
38 Correct 355 ms 334960 KB Output is correct
39 Correct 314 ms 328644 KB Output is correct
40 Correct 336 ms 328716 KB Output is correct
41 Correct 312 ms 322364 KB Output is correct
42 Correct 339 ms 345236 KB Output is correct
43 Correct 339 ms 345216 KB Output is correct
44 Correct 344 ms 345276 KB Output is correct
45 Correct 337 ms 341432 KB Output is correct
46 Correct 263 ms 318584 KB Output is correct
47 Correct 295 ms 321544 KB Output is correct
48 Correct 427 ms 329868 KB Output is correct
49 Correct 426 ms 330820 KB Output is correct
50 Correct 296 ms 318872 KB Output is correct
51 Correct 289 ms 314864 KB Output is correct
52 Correct 399 ms 329072 KB Output is correct
53 Correct 399 ms 329032 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 440944 KB Output is correct
2 Correct 256 ms 400056 KB Output is correct
3 Correct 256 ms 440708 KB Output is correct
4 Correct 168 ms 293768 KB Output is correct
5 Correct 261 ms 441032 KB Output is correct
6 Correct 270 ms 441176 KB Output is correct
7 Correct 263 ms 441004 KB Output is correct
8 Correct 271 ms 441004 KB Output is correct
9 Correct 283 ms 441028 KB Output is correct
10 Correct 266 ms 440824 KB Output is correct
11 Correct 293 ms 440960 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 293804 KB Output is correct
2 Correct 170 ms 293796 KB Output is correct
3 Correct 178 ms 293756 KB Output is correct
4 Correct 178 ms 293828 KB Output is correct
5 Correct 172 ms 293808 KB Output is correct
6 Correct 160 ms 293752 KB Output is correct
7 Correct 877 ms 474512 KB Output is correct
8 Correct 1746 ms 601092 KB Output is correct
9 Correct 1711 ms 600668 KB Output is correct
10 Correct 1735 ms 599900 KB Output is correct
11 Correct 403 ms 466884 KB Output is correct
12 Correct 606 ms 488704 KB Output is correct
13 Correct 642 ms 491868 KB Output is correct

Subtask #7
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 293724 KB Output is correct
2 Correct 159 ms 293800 KB Output is correct
3 Correct 159 ms 293832 KB Output is correct
4 Correct 160 ms 293832 KB Output is correct
5 Correct 168 ms 293828 KB Output is correct
6 Correct 152 ms 293816 KB Output is correct
7 Correct 161 ms 293840 KB Output is correct
8 Correct 189 ms 293764 KB Output is correct
9 Correct 158 ms 293828 KB Output is correct
10 Correct 188 ms 293864 KB Output is correct
11 Correct 171 ms 293868 KB Output is correct
12 Correct 153 ms 293760 KB Output is correct
13 Correct 158 ms 293764 KB Output is correct
14 Correct 157 ms 293728 KB Output is correct
15 Correct 246 ms 293764 KB Output is correct
16 Correct 170 ms 293712 KB Output is correct
17 Correct 171 ms 294456 KB Output is correct
18 Correct 162 ms 294484 KB Output is correct
19 Correct 163 ms 294428 KB Output is correct
20 Correct 176 ms 294176 KB Output is correct
21 Correct 164 ms 294268 KB Output is correct
22 Correct 163 ms 294260 KB Output is correct
23 Correct 165 ms 294212 KB Output is correct
24 Correct 163 ms 294064 KB Output is correct
25 Correct 168 ms 297948 KB Output is correct
26 Correct 180 ms 297980 KB Output is correct
27 Correct 176 ms 298144 KB Output is correct
28 Correct 171 ms 295996 KB Output is correct
29 Correct 183 ms 296796 KB Output is correct
30 Correct 179 ms 296880 KB Output is correct
31 Correct 180 ms 296900 KB Output is correct
32 Correct 190 ms 296808 KB Output is correct
33 Correct 355 ms 334960 KB Output is correct
34 Correct 314 ms 328644 KB Output is correct
35 Correct 336 ms 328716 KB Output is correct
36 Correct 312 ms 322364 KB Output is correct
37 Correct 339 ms 345236 KB Output is correct
38 Correct 339 ms 345216 KB Output is correct
39 Correct 344 ms 345276 KB Output is correct
40 Correct 337 ms 341432 KB Output is correct
41 Correct 263 ms 318584 KB Output is correct
42 Correct 295 ms 321544 KB Output is correct
43 Correct 427 ms 329868 KB Output is correct
44 Correct 426 ms 330820 KB Output is correct
45 Correct 296 ms 318872 KB Output is correct
46 Correct 289 ms 314864 KB Output is correct
47 Correct 399 ms 329072 KB Output is correct
48 Correct 399 ms 329032 KB Output is correct
49 Correct 270 ms 440944 KB Output is correct
50 Correct 256 ms 400056 KB Output is correct
51 Correct 256 ms 440708 KB Output is correct
52 Correct 168 ms 293768 KB Output is correct
53 Correct 261 ms 441032 KB Output is correct
54 Correct 270 ms 441176 KB Output is correct
55 Correct 263 ms 441004 KB Output is correct
56 Correct 271 ms 441004 KB Output is correct
57 Correct 283 ms 441028 KB Output is correct
58 Correct 266 ms 440824 KB Output is correct
59 Correct 293 ms 440960 KB Output is correct
60 Correct 160 ms 293752 KB Output is correct
61 Correct 877 ms 474512 KB Output is correct
62 Correct 1746 ms 601092 KB Output is correct
63 Correct 1711 ms 600668 KB Output is correct
64 Correct 1735 ms 599900 KB Output is correct
65 Correct 403 ms 466884 KB Output is correct
66 Correct 606 ms 488704 KB Output is correct
67 Correct 642 ms 491868 KB Output is correct
68 Correct 191 ms 293804 KB Output is correct
69 Correct 170 ms 293796 KB Output is correct
70 Correct 178 ms 293756 KB Output is correct
71 Correct 178 ms 293828 KB Output is correct
72 Correct 172 ms 293808 KB Output is correct
73 Correct 3241 ms 809460 KB Output is correct
74 Correct 2372 ms 704052 KB Output is correct
75 Correct 3048 ms 703936 KB Output is correct
76 Correct 2153 ms 623428 KB Output is correct
77 Correct 3562 ms 968660 KB Output is correct
78 Correct 2482 ms 568028 KB Output is correct
79 Correct 2780 ms 650112 KB Output is correct
80 Correct 4392 ms 750460 KB Output is correct
81 Correct 2692 ms 584312 KB Output is correct
82 Correct 3620 ms 714112 KB Output is correct
83 Correct 4425 ms 777932 KB Output is correct
84 Correct 2379 ms 567524 KB Output is correct
85 Correct 4222 ms 759476 KB Output is correct
86 Correct 3943 ms 741908 KB Output is correct
87 Correct 2189 ms 753528 KB Output is correct
88 Correct 3727 ms 960604 KB Output is correct
89 Correct 3675 ms 965092 KB Output is correct
90 Correct 3774 ms 967048 KB Output is correct