oj.uz

답안 #212041

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
212041 2020-03-22T06:46:23 Z anonymous Rectangles (IOI19_rect) C++14
100 / 100
 3038 ms 974560 KB 
#include "rect.h"
#include<unordered_set>
#include<vector>
#include<algorithm>
#include<utility>
#define MAXN 2505
using namespace std;
int N,M,A[MAXN][MAXN], Prev[MAXN][MAXN][2];
vector<pair<int,int> > Hor[MAXN][MAXN], Vert[MAXN][MAXN];
vector<pair<int,int>> HorM[MAXN], VertM[MAXN]; 
vector<pair<int,int> > S;

class fenwick {
    int ft[MAXN + 5];
public:
    void add(int v, int p) {
        for (int i=p; i<=MAXN; i+=i&(-i)) {ft[i]+=v;}
    }
    int ask(int p) {
        int res = 0;
        for (int i=p; i>0; i-=i&(-i)) {res+=ft[i];}
        return(res);
    }
} BIT;

void pairs() {
    for (int i=1; i<=N; i++) { //init horizontal
        while (S.size()) {S.pop_back();}
        for (int j=1; j<=M; j++) {
            bool same = false;
            while(S.size() && S.back().first <= A[i][j]) {
                if (A[i][j] == S.back().first) {same=true;}
                if (j - S.back().second > 1) {HorM[i].push_back({S.back().second, j});}
                S.pop_back();
            }
            if (!same && S.size() && j - S.back().second > 1) {HorM[i].push_back({S.back().second, j});}
            S.push_back({A[i][j], j});
        }
    }
    for (int j=1; j<=M; j++) {
        while (S.size()) {S.pop_back();}
        for (int i=1; i<=N; i++) {
            bool same = false;
            while (S.size() && S.back().first <= A[i][j]) {
                if (A[i][j] == S.back().first) {same=true;}
                if (i - S.back().second > 1) {VertM[j].push_back({S.back().second,i});}
                S.pop_back();
            }
            if (!same && S.size() && i - S.back().second > 1) {VertM[j].push_back({S.back().second,i});}
            S.push_back({A[i][j], i});
        }
    }
    for (int i=N; i>=1; i--) {
        for (int k=0; k<HorM[i].size(); k++) {
            pair <int,int> p = HorM[i][k];
            if (Prev[p.first][p.second][0] != i+1) {
                Prev[p.first][p.second][1] = i;
            }
            Prev[p.first][p.second][0] = i;
            Hor[i][p.first].push_back({p.second, Prev[p.first][p.second][1]});
        }
    }
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            Prev[i][j][0] = Prev[i][j][1] = 0;
        }
    }
    for (int j=M; j>=1; j--) {
        for (int k=0; k<VertM[j].size(); k++) {
            pair <int,int> p = VertM[j][k];
            if (Prev[p.first][p.second][0] != j+1) {
                Prev[p.first][p.second][1] = j;
            }
            Prev[p.first][p.second][0] = j;
            Vert[p.first][j].push_back({Prev[p.first][p.second][1], p.second});
        }
    }
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            sort(Hor[i][j].begin(), Hor[i][j].end());
            sort(Vert[i][j].begin(), Vert[i][j].end());
        }
    }
}

long long count_rectangles(vector<vector<int> > a) {
    long long ans = 0;
    N = a.size(), M = a[0].size();
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            A[i+1][j+1]=a[i][j]; //zero index
        }
    }
    pairs();
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            int pt1 = Hor[i+1][j].size()-1, pt2 = Vert[i][j+1].size()-1; 
            while (pt1 >= 0 || pt2 >= 0) {
                if (pt1 == -1 || (pt2 >= 0 && Hor[i+1][j][pt1].first <= Vert[i][j+1][pt2].first+1)) {
                    BIT.add(1, Vert[i][j+1][pt2].second);
                    pt2--;
                } else {
                    ans += (long long) BIT.ask(Hor[i+1][j][pt1].second+1) - BIT.ask(i+1);
                    pt1--;
                }
            }
            for (auto v: Vert[i][j+1]) {
                BIT.add(-1, v.second);
            }
        }
    }
    return(ans);
}

Compilation message

rect.cpp: In function 'void pairs()':
rect.cpp:54:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int k=0; k<HorM[i].size(); k++) {
                       ~^~~~~~~~~~~~~~~
rect.cpp:69:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int k=0; k<VertM[j].size(); k++) {
                       ~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 295288 KB Output is correct
2 Correct 160 ms 295292 KB Output is correct
3 Correct 161 ms 295416 KB Output is correct
4 Correct 166 ms 295416 KB Output is correct
5 Correct 164 ms 295416 KB Output is correct
6 Correct 170 ms 295544 KB Output is correct
7 Correct 169 ms 295288 KB Output is correct
8 Correct 171 ms 295416 KB Output is correct
9 Correct 162 ms 295416 KB Output is correct
10 Correct 161 ms 295416 KB Output is correct
11 Correct 168 ms 295416 KB Output is correct
12 Correct 164 ms 295544 KB Output is correct
13 Correct 159 ms 295160 KB Output is correct
14 Correct 180 ms 295288 KB Output is correct
15 Correct 175 ms 295340 KB Output is correct
16 Correct 164 ms 295160 KB Output is correct
17 Correct 165 ms 295160 KB Output is correct
18 Correct 164 ms 295160 KB Output is correct
19 Correct 159 ms 295420 KB Output is correct
20 Correct 166 ms 295416 KB Output is correct
21 Correct 161 ms 295160 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 295288 KB Output is correct
2 Correct 160 ms 295292 KB Output is correct
3 Correct 161 ms 295416 KB Output is correct
4 Correct 166 ms 295416 KB Output is correct
5 Correct 164 ms 295416 KB Output is correct
6 Correct 170 ms 295544 KB Output is correct
7 Correct 169 ms 295288 KB Output is correct
8 Correct 171 ms 295416 KB Output is correct
9 Correct 162 ms 295416 KB Output is correct
10 Correct 161 ms 295416 KB Output is correct
11 Correct 168 ms 295416 KB Output is correct
12 Correct 164 ms 295544 KB Output is correct
13 Correct 159 ms 295160 KB Output is correct
14 Correct 180 ms 295288 KB Output is correct
15 Correct 175 ms 295340 KB Output is correct
16 Correct 164 ms 295160 KB Output is correct
17 Correct 172 ms 296568 KB Output is correct
18 Correct 165 ms 296568 KB Output is correct
19 Correct 165 ms 296568 KB Output is correct
20 Correct 160 ms 296056 KB Output is correct
21 Correct 163 ms 296312 KB Output is correct
22 Correct 165 ms 296312 KB Output is correct
23 Correct 163 ms 296312 KB Output is correct
24 Correct 169 ms 296056 KB Output is correct
25 Correct 165 ms 295160 KB Output is correct
26 Correct 164 ms 295160 KB Output is correct
27 Correct 159 ms 295420 KB Output is correct
28 Correct 166 ms 295416 KB Output is correct
29 Correct 161 ms 295160 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 295288 KB Output is correct
2 Correct 160 ms 295292 KB Output is correct
3 Correct 161 ms 295416 KB Output is correct
4 Correct 166 ms 295416 KB Output is correct
5 Correct 164 ms 295416 KB Output is correct
6 Correct 170 ms 295544 KB Output is correct
7 Correct 169 ms 295288 KB Output is correct
8 Correct 171 ms 295416 KB Output is correct
9 Correct 162 ms 295416 KB Output is correct
10 Correct 161 ms 295416 KB Output is correct
11 Correct 168 ms 295416 KB Output is correct
12 Correct 164 ms 295544 KB Output is correct
13 Correct 159 ms 295160 KB Output is correct
14 Correct 180 ms 295288 KB Output is correct
15 Correct 175 ms 295340 KB Output is correct
16 Correct 164 ms 295160 KB Output is correct
17 Correct 172 ms 296568 KB Output is correct
18 Correct 165 ms 296568 KB Output is correct
19 Correct 165 ms 296568 KB Output is correct
20 Correct 160 ms 296056 KB Output is correct
21 Correct 163 ms 296312 KB Output is correct
22 Correct 165 ms 296312 KB Output is correct
23 Correct 163 ms 296312 KB Output is correct
24 Correct 169 ms 296056 KB Output is correct
25 Correct 211 ms 301048 KB Output is correct
26 Correct 175 ms 301048 KB Output is correct
27 Correct 177 ms 301176 KB Output is correct
28 Correct 169 ms 298924 KB Output is correct
29 Correct 177 ms 299896 KB Output is correct
30 Correct 179 ms 300152 KB Output is correct
31 Correct 180 ms 300120 KB Output is correct
32 Correct 179 ms 300024 KB Output is correct
33 Correct 165 ms 295160 KB Output is correct
34 Correct 164 ms 295160 KB Output is correct
35 Correct 159 ms 295420 KB Output is correct
36 Correct 166 ms 295416 KB Output is correct
37 Correct 161 ms 295160 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 295288 KB Output is correct
2 Correct 160 ms 295292 KB Output is correct
3 Correct 161 ms 295416 KB Output is correct
4 Correct 166 ms 295416 KB Output is correct
5 Correct 164 ms 295416 KB Output is correct
6 Correct 170 ms 295544 KB Output is correct
7 Correct 169 ms 295288 KB Output is correct
8 Correct 171 ms 295416 KB Output is correct
9 Correct 162 ms 295416 KB Output is correct
10 Correct 161 ms 295416 KB Output is correct
11 Correct 168 ms 295416 KB Output is correct
12 Correct 164 ms 295544 KB Output is correct
13 Correct 159 ms 295160 KB Output is correct
14 Correct 180 ms 295288 KB Output is correct
15 Correct 175 ms 295340 KB Output is correct
16 Correct 164 ms 295160 KB Output is correct
17 Correct 172 ms 296568 KB Output is correct
18 Correct 165 ms 296568 KB Output is correct
19 Correct 165 ms 296568 KB Output is correct
20 Correct 160 ms 296056 KB Output is correct
21 Correct 163 ms 296312 KB Output is correct
22 Correct 165 ms 296312 KB Output is correct
23 Correct 163 ms 296312 KB Output is correct
24 Correct 169 ms 296056 KB Output is correct
25 Correct 211 ms 301048 KB Output is correct
26 Correct 175 ms 301048 KB Output is correct
27 Correct 177 ms 301176 KB Output is correct
28 Correct 169 ms 298924 KB Output is correct
29 Correct 177 ms 299896 KB Output is correct
30 Correct 179 ms 300152 KB Output is correct
31 Correct 180 ms 300120 KB Output is correct
32 Correct 179 ms 300024 KB Output is correct
33 Correct 258 ms 332024 KB Output is correct
34 Correct 272 ms 327420 KB Output is correct
35 Correct 245 ms 327292 KB Output is correct
36 Correct 232 ms 322552 KB Output is correct
37 Correct 318 ms 352920 KB Output is correct
38 Correct 306 ms 352760 KB Output is correct
39 Correct 310 ms 352888 KB Output is correct
40 Correct 310 ms 349688 KB Output is correct
41 Correct 244 ms 321632 KB Output is correct
42 Correct 256 ms 326776 KB Output is correct
43 Correct 353 ms 340312 KB Output is correct
44 Correct 359 ms 340352 KB Output is correct
45 Correct 260 ms 322808 KB Output is correct
46 Correct 273 ms 319424 KB Output is correct
47 Correct 376 ms 338680 KB Output is correct
48 Correct 376 ms 338804 KB Output is correct
49 Correct 165 ms 295160 KB Output is correct
50 Correct 164 ms 295160 KB Output is correct
51 Correct 159 ms 295420 KB Output is correct
52 Correct 166 ms 295416 KB Output is correct
53 Correct 161 ms 295160 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 305912 KB Output is correct
2 Correct 170 ms 304248 KB Output is correct
3 Correct 169 ms 295288 KB Output is correct
4 Correct 167 ms 295136 KB Output is correct
5 Correct 177 ms 304760 KB Output is correct
6 Correct 184 ms 304632 KB Output is correct
7 Correct 190 ms 304780 KB Output is correct
8 Correct 188 ms 303968 KB Output is correct
9 Correct 171 ms 303736 KB Output is correct
10 Correct 166 ms 300536 KB Output is correct
11 Correct 178 ms 303224 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 295288 KB Output is correct
2 Correct 647 ms 416216 KB Output is correct
3 Correct 1253 ms 555408 KB Output is correct
4 Correct 1206 ms 556568 KB Output is correct
5 Correct 1242 ms 556664 KB Output is correct
6 Correct 315 ms 349432 KB Output is correct
7 Correct 465 ms 415636 KB Output is correct
8 Correct 478 ms 418808 KB Output is correct
9 Correct 165 ms 295160 KB Output is correct
10 Correct 164 ms 295160 KB Output is correct
11 Correct 159 ms 295420 KB Output is correct
12 Correct 166 ms 295416 KB Output is correct
13 Correct 161 ms 295160 KB Output is correct

Subtask #7
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 295288 KB Output is correct
2 Correct 160 ms 295292 KB Output is correct
3 Correct 161 ms 295416 KB Output is correct
4 Correct 166 ms 295416 KB Output is correct
5 Correct 164 ms 295416 KB Output is correct
6 Correct 170 ms 295544 KB Output is correct
7 Correct 169 ms 295288 KB Output is correct
8 Correct 171 ms 295416 KB Output is correct
9 Correct 162 ms 295416 KB Output is correct
10 Correct 161 ms 295416 KB Output is correct
11 Correct 168 ms 295416 KB Output is correct
12 Correct 164 ms 295544 KB Output is correct
13 Correct 159 ms 295160 KB Output is correct
14 Correct 180 ms 295288 KB Output is correct
15 Correct 175 ms 295340 KB Output is correct
16 Correct 164 ms 295160 KB Output is correct
17 Correct 172 ms 296568 KB Output is correct
18 Correct 165 ms 296568 KB Output is correct
19 Correct 165 ms 296568 KB Output is correct
20 Correct 160 ms 296056 KB Output is correct
21 Correct 163 ms 296312 KB Output is correct
22 Correct 165 ms 296312 KB Output is correct
23 Correct 163 ms 296312 KB Output is correct
24 Correct 169 ms 296056 KB Output is correct
25 Correct 211 ms 301048 KB Output is correct
26 Correct 175 ms 301048 KB Output is correct
27 Correct 177 ms 301176 KB Output is correct
28 Correct 169 ms 298924 KB Output is correct
29 Correct 177 ms 299896 KB Output is correct
30 Correct 179 ms 300152 KB Output is correct
31 Correct 180 ms 300120 KB Output is correct
32 Correct 179 ms 300024 KB Output is correct
33 Correct 258 ms 332024 KB Output is correct
34 Correct 272 ms 327420 KB Output is correct
35 Correct 245 ms 327292 KB Output is correct
36 Correct 232 ms 322552 KB Output is correct
37 Correct 318 ms 352920 KB Output is correct
38 Correct 306 ms 352760 KB Output is correct
39 Correct 310 ms 352888 KB Output is correct
40 Correct 310 ms 349688 KB Output is correct
41 Correct 244 ms 321632 KB Output is correct
42 Correct 256 ms 326776 KB Output is correct
43 Correct 353 ms 340312 KB Output is correct
44 Correct 359 ms 340352 KB Output is correct
45 Correct 260 ms 322808 KB Output is correct
46 Correct 273 ms 319424 KB Output is correct
47 Correct 376 ms 338680 KB Output is correct
48 Correct 376 ms 338804 KB Output is correct
49 Correct 169 ms 305912 KB Output is correct
50 Correct 170 ms 304248 KB Output is correct
51 Correct 169 ms 295288 KB Output is correct
52 Correct 167 ms 295136 KB Output is correct
53 Correct 177 ms 304760 KB Output is correct
54 Correct 184 ms 304632 KB Output is correct
55 Correct 190 ms 304780 KB Output is correct
56 Correct 188 ms 303968 KB Output is correct
57 Correct 171 ms 303736 KB Output is correct
58 Correct 166 ms 300536 KB Output is correct
59 Correct 178 ms 303224 KB Output is correct
60 Correct 182 ms 295288 KB Output is correct
61 Correct 647 ms 416216 KB Output is correct
62 Correct 1253 ms 555408 KB Output is correct
63 Correct 1206 ms 556568 KB Output is correct
64 Correct 1242 ms 556664 KB Output is correct
65 Correct 315 ms 349432 KB Output is correct
66 Correct 465 ms 415636 KB Output is correct
67 Correct 478 ms 418808 KB Output is correct
68 Correct 1746 ms 675580 KB Output is correct
69 Correct 1646 ms 608480 KB Output is correct
70 Correct 1185 ms 608376 KB Output is correct
71 Correct 1038 ms 541432 KB Output is correct
72 Correct 2960 ms 927164 KB Output is correct
73 Correct 1855 ms 585408 KB Output is correct
74 Correct 1921 ms 624120 KB Output is correct
75 Correct 2903 ms 764920 KB Output is correct
76 Correct 1866 ms 616656 KB Output is correct
77 Correct 2440 ms 720040 KB Output is correct
78 Correct 3011 ms 816496 KB Output is correct
79 Correct 1720 ms 587784 KB Output is correct
80 Correct 2956 ms 792900 KB Output is correct
81 Correct 2858 ms 777840 KB Output is correct
82 Correct 1728 ms 736120 KB Output is correct
83 Correct 3038 ms 973736 KB Output is correct
84 Correct 2869 ms 974560 KB Output is correct
85 Correct 2916 ms 974544 KB Output is correct
86 Correct 165 ms 295160 KB Output is correct
87 Correct 164 ms 295160 KB Output is correct
88 Correct 159 ms 295420 KB Output is correct
89 Correct 166 ms 295416 KB Output is correct
90 Correct 161 ms 295160 KB Output is correct