oj.uz

답안 #473428

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 293740 KB Output is correct
2 Correct 181 ms 293844 KB Output is correct
3 Correct 166 ms 293828 KB Output is correct
4 Correct 159 ms 293804 KB Output is correct
5 Correct 156 ms 293824 KB Output is correct
6 Correct 155 ms 293816 KB Output is correct
7 Correct 156 ms 293820 KB Output is correct
8 Correct 161 ms 293784 KB Output is correct
9 Correct 155 ms 293784 KB Output is correct
10 Correct 163 ms 293856 KB Output is correct
11 Correct 157 ms 293864 KB Output is correct
12 Correct 161 ms 293840 KB Output is correct
13 Correct 160 ms 293716 KB Output is correct
14 Correct 157 ms 293828 KB Output is correct
15 Correct 156 ms 293816 KB Output is correct
16 Correct 160 ms 293716 KB Output is correct
17 Correct 161 ms 293716 KB Output is correct
18 Correct 163 ms 293876 KB Output is correct
19 Correct 156 ms 293776 KB Output is correct
20 Correct 159 ms 293732 KB Output is correct
21 Correct 157 ms 293720 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 293740 KB Output is correct
2 Correct 181 ms 293844 KB Output is correct
3 Correct 166 ms 293828 KB Output is correct
4 Correct 159 ms 293804 KB Output is correct
5 Correct 156 ms 293824 KB Output is correct
6 Correct 155 ms 293816 KB Output is correct
7 Correct 156 ms 293820 KB Output is correct
8 Correct 161 ms 293784 KB Output is correct
9 Correct 155 ms 293784 KB Output is correct
10 Correct 163 ms 293856 KB Output is correct
11 Correct 157 ms 293864 KB Output is correct
12 Correct 161 ms 293840 KB Output is correct
13 Correct 160 ms 293716 KB Output is correct
14 Correct 157 ms 293828 KB Output is correct
15 Correct 156 ms 293816 KB Output is correct
16 Correct 160 ms 293716 KB Output is correct
17 Correct 161 ms 293716 KB Output is correct
18 Correct 163 ms 293876 KB Output is correct
19 Correct 156 ms 293776 KB Output is correct
20 Correct 159 ms 293732 KB Output is correct
21 Correct 157 ms 293720 KB Output is correct
22 Correct 157 ms 294424 KB Output is correct
23 Correct 230 ms 294432 KB Output is correct
24 Correct 163 ms 294384 KB Output is correct
25 Correct 163 ms 294232 KB Output is correct
26 Correct 161 ms 294212 KB Output is correct
27 Correct 160 ms 294200 KB Output is correct
28 Correct 179 ms 294244 KB Output is correct
29 Correct 164 ms 294144 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 293740 KB Output is correct
2 Correct 181 ms 293844 KB Output is correct
3 Correct 166 ms 293828 KB Output is correct
4 Correct 159 ms 293804 KB Output is correct
5 Correct 156 ms 293824 KB Output is correct
6 Correct 155 ms 293816 KB Output is correct
7 Correct 156 ms 293820 KB Output is correct
8 Correct 161 ms 293784 KB Output is correct
9 Correct 155 ms 293784 KB Output is correct
10 Correct 163 ms 293856 KB Output is correct
11 Correct 157 ms 293864 KB Output is correct
12 Correct 161 ms 293840 KB Output is correct
13 Correct 160 ms 293716 KB Output is correct
14 Correct 157 ms 293828 KB Output is correct
15 Correct 156 ms 293816 KB Output is correct
16 Correct 160 ms 293716 KB Output is correct
17 Correct 157 ms 294424 KB Output is correct
18 Correct 230 ms 294432 KB Output is correct
19 Correct 163 ms 294384 KB Output is correct
20 Correct 163 ms 294232 KB Output is correct
21 Correct 161 ms 294212 KB Output is correct
22 Correct 160 ms 294200 KB Output is correct
23 Correct 179 ms 294244 KB Output is correct
24 Correct 164 ms 294144 KB Output is correct
25 Correct 161 ms 293716 KB Output is correct
26 Correct 163 ms 293876 KB Output is correct
27 Correct 156 ms 293776 KB Output is correct
28 Correct 159 ms 293732 KB Output is correct
29 Correct 157 ms 293720 KB Output is correct
30 Correct 196 ms 297876 KB Output is correct
31 Correct 178 ms 297936 KB Output is correct
32 Correct 175 ms 298112 KB Output is correct
33 Correct 198 ms 296040 KB Output is correct
34 Correct 183 ms 296724 KB Output is correct
35 Correct 180 ms 296892 KB Output is correct
36 Correct 177 ms 296744 KB Output is correct
37 Correct 182 ms 296772 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 293740 KB Output is correct
2 Correct 181 ms 293844 KB Output is correct
3 Correct 166 ms 293828 KB Output is correct
4 Correct 159 ms 293804 KB Output is correct
5 Correct 156 ms 293824 KB Output is correct
6 Correct 155 ms 293816 KB Output is correct
7 Correct 156 ms 293820 KB Output is correct
8 Correct 161 ms 293784 KB Output is correct
9 Correct 155 ms 293784 KB Output is correct
10 Correct 163 ms 293856 KB Output is correct
11 Correct 157 ms 293864 KB Output is correct
12 Correct 161 ms 293840 KB Output is correct
13 Correct 160 ms 293716 KB Output is correct
14 Correct 157 ms 293828 KB Output is correct
15 Correct 156 ms 293816 KB Output is correct
16 Correct 160 ms 293716 KB Output is correct
17 Correct 157 ms 294424 KB Output is correct
18 Correct 230 ms 294432 KB Output is correct
19 Correct 163 ms 294384 KB Output is correct
20 Correct 163 ms 294232 KB Output is correct
21 Correct 161 ms 294212 KB Output is correct
22 Correct 160 ms 294200 KB Output is correct
23 Correct 179 ms 294244 KB Output is correct
24 Correct 164 ms 294144 KB Output is correct
25 Correct 196 ms 297876 KB Output is correct
26 Correct 178 ms 297936 KB Output is correct
27 Correct 175 ms 298112 KB Output is correct
28 Correct 198 ms 296040 KB Output is correct
29 Correct 183 ms 296724 KB Output is correct
30 Correct 180 ms 296892 KB Output is correct
31 Correct 177 ms 296744 KB Output is correct
32 Correct 182 ms 296772 KB Output is correct
33 Correct 161 ms 293716 KB Output is correct
34 Correct 163 ms 293876 KB Output is correct
35 Correct 156 ms 293776 KB Output is correct
36 Correct 159 ms 293732 KB Output is correct
37 Correct 157 ms 293720 KB Output is correct
38 Correct 347 ms 335336 KB Output is correct
39 Correct 358 ms 329024 KB Output is correct
40 Correct 337 ms 329176 KB Output is correct
41 Correct 321 ms 322912 KB Output is correct
42 Correct 339 ms 345872 KB Output is correct
43 Correct 357 ms 345796 KB Output is correct
44 Correct 341 ms 346252 KB Output is correct
45 Correct 329 ms 342124 KB Output is correct
46 Correct 263 ms 318524 KB Output is correct
47 Correct 298 ms 321544 KB Output is correct
48 Correct 420 ms 329852 KB Output is correct
49 Correct 428 ms 331956 KB Output is correct
50 Correct 289 ms 318788 KB Output is correct
51 Correct 296 ms 314900 KB Output is correct
52 Correct 400 ms 329028 KB Output is correct
53 Correct 391 ms 330128 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 266 ms 441096 KB Output is correct
2 Correct 233 ms 400084 KB Output is correct
3 Correct 297 ms 440772 KB Output is correct
4 Correct 159 ms 293828 KB Output is correct
5 Correct 267 ms 441096 KB Output is correct
6 Correct 269 ms 441120 KB Output is correct
7 Correct 277 ms 441120 KB Output is correct
8 Correct 265 ms 441068 KB Output is correct
9 Correct 259 ms 440952 KB Output is correct
10 Correct 268 ms 440812 KB Output is correct
11 Correct 261 ms 440876 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 293716 KB Output is correct
2 Correct 163 ms 293876 KB Output is correct
3 Correct 156 ms 293776 KB Output is correct
4 Correct 159 ms 293732 KB Output is correct
5 Correct 157 ms 293720 KB Output is correct
6 Correct 157 ms 293756 KB Output is correct
7 Correct 897 ms 475796 KB Output is correct
8 Correct 1787 ms 604080 KB Output is correct
9 Correct 1692 ms 608552 KB Output is correct
10 Correct 1744 ms 606656 KB Output is correct
11 Correct 404 ms 471004 KB Output is correct
12 Correct 639 ms 492848 KB Output is correct
13 Correct 643 ms 495828 KB Output is correct

Subtask #7
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 293740 KB Output is correct
2 Correct 181 ms 293844 KB Output is correct
3 Correct 166 ms 293828 KB Output is correct
4 Correct 159 ms 293804 KB Output is correct
5 Correct 156 ms 293824 KB Output is correct
6 Correct 155 ms 293816 KB Output is correct
7 Correct 156 ms 293820 KB Output is correct
8 Correct 161 ms 293784 KB Output is correct
9 Correct 155 ms 293784 KB Output is correct
10 Correct 163 ms 293856 KB Output is correct
11 Correct 157 ms 293864 KB Output is correct
12 Correct 161 ms 293840 KB Output is correct
13 Correct 160 ms 293716 KB Output is correct
14 Correct 157 ms 293828 KB Output is correct
15 Correct 156 ms 293816 KB Output is correct
16 Correct 160 ms 293716 KB Output is correct
17 Correct 157 ms 294424 KB Output is correct
18 Correct 230 ms 294432 KB Output is correct
19 Correct 163 ms 294384 KB Output is correct
20 Correct 163 ms 294232 KB Output is correct
21 Correct 161 ms 294212 KB Output is correct
22 Correct 160 ms 294200 KB Output is correct
23 Correct 179 ms 294244 KB Output is correct
24 Correct 164 ms 294144 KB Output is correct
25 Correct 196 ms 297876 KB Output is correct
26 Correct 178 ms 297936 KB Output is correct
27 Correct 175 ms 298112 KB Output is correct
28 Correct 198 ms 296040 KB Output is correct
29 Correct 183 ms 296724 KB Output is correct
30 Correct 180 ms 296892 KB Output is correct
31 Correct 177 ms 296744 KB Output is correct
32 Correct 182 ms 296772 KB Output is correct
33 Correct 347 ms 335336 KB Output is correct
34 Correct 358 ms 329024 KB Output is correct
35 Correct 337 ms 329176 KB Output is correct
36 Correct 321 ms 322912 KB Output is correct
37 Correct 339 ms 345872 KB Output is correct
38 Correct 357 ms 345796 KB Output is correct
39 Correct 341 ms 346252 KB Output is correct
40 Correct 329 ms 342124 KB Output is correct
41 Correct 263 ms 318524 KB Output is correct
42 Correct 298 ms 321544 KB Output is correct
43 Correct 420 ms 329852 KB Output is correct
44 Correct 428 ms 331956 KB Output is correct
45 Correct 289 ms 318788 KB Output is correct
46 Correct 296 ms 314900 KB Output is correct
47 Correct 400 ms 329028 KB Output is correct
48 Correct 391 ms 330128 KB Output is correct
49 Correct 266 ms 441096 KB Output is correct
50 Correct 233 ms 400084 KB Output is correct
51 Correct 297 ms 440772 KB Output is correct
52 Correct 159 ms 293828 KB Output is correct
53 Correct 267 ms 441096 KB Output is correct
54 Correct 269 ms 441120 KB Output is correct
55 Correct 277 ms 441120 KB Output is correct
56 Correct 265 ms 441068 KB Output is correct
57 Correct 259 ms 440952 KB Output is correct
58 Correct 268 ms 440812 KB Output is correct
59 Correct 261 ms 440876 KB Output is correct
60 Correct 157 ms 293756 KB Output is correct
61 Correct 897 ms 475796 KB Output is correct
62 Correct 1787 ms 604080 KB Output is correct
63 Correct 1692 ms 608552 KB Output is correct
64 Correct 1744 ms 606656 KB Output is correct
65 Correct 404 ms 471004 KB Output is correct
66 Correct 639 ms 492848 KB Output is correct
67 Correct 643 ms 495828 KB Output is correct
68 Correct 161 ms 293716 KB Output is correct
69 Correct 163 ms 293876 KB Output is correct
70 Correct 156 ms 293776 KB Output is correct
71 Correct 159 ms 293732 KB Output is correct
72 Correct 157 ms 293720 KB Output is correct
73 Correct 3355 ms 789704 KB Output is correct
74 Correct 2342 ms 703952 KB Output is correct
75 Correct 3091 ms 703948 KB Output is correct
76 Correct 2188 ms 623120 KB Output is correct
77 Correct 3625 ms 933884 KB Output is correct
78 Correct 2587 ms 568116 KB Output is correct
79 Correct 2748 ms 650036 KB Output is correct
80 Correct 4536 ms 733956 KB Output is correct
81 Correct 2725 ms 562572 KB Output is correct
82 Correct 3682 ms 685260 KB Output is correct
83 Correct 4525 ms 742968 KB Output is correct
84 Correct 2462 ms 567372 KB Output is correct
85 Correct 4190 ms 724604 KB Output is correct
86 Correct 4003 ms 708012 KB Output is correct
87 Correct 2184 ms 731684 KB Output is correct
88 Correct 3593 ms 932928 KB Output is correct
89 Correct 3683 ms 927880 KB Output is correct
90 Correct 3584 ms 924356 KB Output is correct