oj.uz

답안 #678285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678285 2023-01-05T11:50:40 Z someone Rectangles (IOI19_rect) C++14
100 / 100
 3142 ms 841612 KB 
#include <bits/stdc++.h>
using namespace std;
 
struct Req {
    bool isUpd;
    int x, y;
};
 
const int N = 2500 + 42, M = 1 << 12;
 
vector<int> val;
vector<pair<int, int>> fin[N][N][2];
int n, m, pre[N][N], nb[N][N], sum[2*M];

inline int add(int l, int r, int i) {
    if(pre[l][r] != i+1)
        nb[l][r] = 0;
    pre[l][r] = i;
    return ++nb[l][r];
}

void upd(int i, int v) {
    i += M;
    while(i) {
        sum[i] += v;
        i >>= 1;
    }
}

int getVal(int i) {
    i += M;
    int ans = sum[i];
    while(i) {
        if(i & 1)
            ans += sum[i-1];
        i >>= 1;
    }
    return ans;
}
 
long long count_rectangles(vector<vector<int>> a) {
    n = (int)a.size();
    m = (int)a[0].size();
 
    for(int i = n-2; i > 0; i--) {
        vector<int> maxi;
        for(int j = 0; j < m; j++) {
            while(!maxi.empty() && a[i][maxi.back()] < a[i][j])
                maxi.pop_back();
            if(!maxi.empty() && a[i][maxi.back()] != a[i][j] && maxi.back() < j-1)
                fin[i][maxi.back()+1][0].push_back({j-1, add(maxi.back()+1, j-1, i)-1});
            maxi.push_back(j);
        }
        maxi.clear();
        for(int j = m-1; j > -1; j--) {
            while(!maxi.empty() && a[i][maxi.back()] < a[i][j])
                maxi.pop_back();
            if(!maxi.empty() && j+1 < maxi.back())
                fin[i][j+1][0].push_back({maxi.back()-1, add(j+1, maxi.back()-1, i)-1});
            maxi.push_back(j);
        }
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            nb[i][j] = pre[i][j] = 0;
    for(int j = m-2; j > 0; j--) {
        vector<int> maxi;
        for(int i = 0; i < n; i++) {
            while(!maxi.empty() && a[maxi.back()][j] < a[i][j])
                maxi.pop_back();
            if(!maxi.empty() && a[maxi.back()][j] != a[i][j] && maxi.back() < i-1)
                fin[maxi.back()+1][j][1].push_back({i-1, add(maxi.back()+1, i-1, j)-1});
            maxi.push_back(i);
        }
        maxi.clear();
        for(int i = n-1; i > -1; i--) {
            while(!maxi.empty() && a[maxi.back()][j] < a[i][j])
                maxi.pop_back();
            if(!maxi.empty() && i+1 < maxi.back())
                fin[i+1][j][1].push_back({maxi.back()-1, add(i+1, maxi.back()-1, j)-1});
            maxi.push_back(i);
        }
    }
    
    int ans = 0;
    for(int i = 1; i < n-1; i++) {
        for(int j = 1; j < m-1; j++) {
            vector<Req> req;
            for(auto pii : fin[i][j][0])
                req.push_back({true, pii.first - j, pii.second});
            for(auto pii : fin[i][j][1])
                req.push_back({false, pii.second, pii.first - i});
            sort(req.begin(), req.end(),
            [](Req a, Req b) {
                if(a.y == b.y)
                    return a.isUpd && !b.isUpd;
                return a.y > b.y;
            });
            for(Req q : req) {
                if(q.isUpd)
                    upd(q.x, 1);
                else
                    ans += getVal(q.x);
            }
            for(Req q : req)
                if(q.isUpd)
                    upd(q.x, -1);
        }
    }
    return ans;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 303724 KB Output is correct
2 Correct 135 ms 304092 KB Output is correct
3 Correct 137 ms 304000 KB Output is correct
4 Correct 139 ms 304116 KB Output is correct
5 Correct 132 ms 303944 KB Output is correct
6 Correct 134 ms 303988 KB Output is correct
7 Correct 142 ms 304060 KB Output is correct
8 Correct 138 ms 304012 KB Output is correct
9 Correct 144 ms 304008 KB Output is correct
10 Correct 133 ms 303988 KB Output is correct
11 Correct 132 ms 304072 KB Output is correct
12 Correct 137 ms 304088 KB Output is correct
13 Correct 134 ms 303780 KB Output is correct
14 Correct 131 ms 303772 KB Output is correct
15 Correct 138 ms 303752 KB Output is correct
16 Correct 136 ms 303820 KB Output is correct
17 Correct 147 ms 303732 KB Output is correct
18 Correct 133 ms 303776 KB Output is correct
19 Correct 141 ms 303948 KB Output is correct
20 Correct 144 ms 303996 KB Output is correct
21 Correct 143 ms 303824 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 303724 KB Output is correct
2 Correct 135 ms 304092 KB Output is correct
3 Correct 137 ms 304000 KB Output is correct
4 Correct 139 ms 304116 KB Output is correct
5 Correct 132 ms 303944 KB Output is correct
6 Correct 134 ms 303988 KB Output is correct
7 Correct 142 ms 304060 KB Output is correct
8 Correct 138 ms 304012 KB Output is correct
9 Correct 144 ms 304008 KB Output is correct
10 Correct 133 ms 303988 KB Output is correct
11 Correct 132 ms 304072 KB Output is correct
12 Correct 137 ms 304088 KB Output is correct
13 Correct 134 ms 303780 KB Output is correct
14 Correct 131 ms 303772 KB Output is correct
15 Correct 138 ms 303752 KB Output is correct
16 Correct 136 ms 303820 KB Output is correct
17 Correct 147 ms 303732 KB Output is correct
18 Correct 133 ms 303776 KB Output is correct
19 Correct 141 ms 303948 KB Output is correct
20 Correct 144 ms 303996 KB Output is correct
21 Correct 143 ms 303824 KB Output is correct
22 Correct 138 ms 304820 KB Output is correct
23 Correct 143 ms 304936 KB Output is correct
24 Correct 147 ms 304972 KB Output is correct
25 Correct 138 ms 304660 KB Output is correct
26 Correct 145 ms 304652 KB Output is correct
27 Correct 133 ms 304680 KB Output is correct
28 Correct 136 ms 304696 KB Output is correct
29 Correct 143 ms 304652 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 303724 KB Output is correct
2 Correct 135 ms 304092 KB Output is correct
3 Correct 137 ms 304000 KB Output is correct
4 Correct 139 ms 304116 KB Output is correct
5 Correct 132 ms 303944 KB Output is correct
6 Correct 134 ms 303988 KB Output is correct
7 Correct 142 ms 304060 KB Output is correct
8 Correct 138 ms 304012 KB Output is correct
9 Correct 144 ms 304008 KB Output is correct
10 Correct 133 ms 303988 KB Output is correct
11 Correct 132 ms 304072 KB Output is correct
12 Correct 137 ms 304088 KB Output is correct
13 Correct 134 ms 303780 KB Output is correct
14 Correct 131 ms 303772 KB Output is correct
15 Correct 138 ms 303752 KB Output is correct
16 Correct 136 ms 303820 KB Output is correct
17 Correct 138 ms 304820 KB Output is correct
18 Correct 143 ms 304936 KB Output is correct
19 Correct 147 ms 304972 KB Output is correct
20 Correct 138 ms 304660 KB Output is correct
21 Correct 145 ms 304652 KB Output is correct
22 Correct 133 ms 304680 KB Output is correct
23 Correct 136 ms 304696 KB Output is correct
24 Correct 143 ms 304652 KB Output is correct
25 Correct 147 ms 303732 KB Output is correct
26 Correct 133 ms 303776 KB Output is correct
27 Correct 141 ms 303948 KB Output is correct
28 Correct 144 ms 303996 KB Output is correct
29 Correct 143 ms 303824 KB Output is correct
30 Correct 145 ms 308716 KB Output is correct
31 Correct 147 ms 308640 KB Output is correct
32 Correct 149 ms 308748 KB Output is correct
33 Correct 141 ms 306928 KB Output is correct
34 Correct 148 ms 307556 KB Output is correct
35 Correct 147 ms 307748 KB Output is correct
36 Correct 164 ms 307620 KB Output is correct
37 Correct 146 ms 307584 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 303724 KB Output is correct
2 Correct 135 ms 304092 KB Output is correct
3 Correct 137 ms 304000 KB Output is correct
4 Correct 139 ms 304116 KB Output is correct
5 Correct 132 ms 303944 KB Output is correct
6 Correct 134 ms 303988 KB Output is correct
7 Correct 142 ms 304060 KB Output is correct
8 Correct 138 ms 304012 KB Output is correct
9 Correct 144 ms 304008 KB Output is correct
10 Correct 133 ms 303988 KB Output is correct
11 Correct 132 ms 304072 KB Output is correct
12 Correct 137 ms 304088 KB Output is correct
13 Correct 134 ms 303780 KB Output is correct
14 Correct 131 ms 303772 KB Output is correct
15 Correct 138 ms 303752 KB Output is correct
16 Correct 136 ms 303820 KB Output is correct
17 Correct 138 ms 304820 KB Output is correct
18 Correct 143 ms 304936 KB Output is correct
19 Correct 147 ms 304972 KB Output is correct
20 Correct 138 ms 304660 KB Output is correct
21 Correct 145 ms 304652 KB Output is correct
22 Correct 133 ms 304680 KB Output is correct
23 Correct 136 ms 304696 KB Output is correct
24 Correct 143 ms 304652 KB Output is correct
25 Correct 145 ms 308716 KB Output is correct
26 Correct 147 ms 308640 KB Output is correct
27 Correct 149 ms 308748 KB Output is correct
28 Correct 141 ms 306928 KB Output is correct
29 Correct 148 ms 307556 KB Output is correct
30 Correct 147 ms 307748 KB Output is correct
31 Correct 164 ms 307620 KB Output is correct
32 Correct 146 ms 307584 KB Output is correct
33 Correct 147 ms 303732 KB Output is correct
34 Correct 133 ms 303776 KB Output is correct
35 Correct 141 ms 303948 KB Output is correct
36 Correct 144 ms 303996 KB Output is correct
37 Correct 143 ms 303824 KB Output is correct
38 Correct 224 ms 335572 KB Output is correct
39 Correct 213 ms 330692 KB Output is correct
40 Correct 198 ms 330744 KB Output is correct
41 Correct 186 ms 326012 KB Output is correct
42 Correct 311 ms 350916 KB Output is correct
43 Correct 299 ms 350868 KB Output is correct
44 Correct 310 ms 351284 KB Output is correct
45 Correct 302 ms 348592 KB Output is correct
46 Correct 203 ms 325716 KB Output is correct
47 Correct 236 ms 328160 KB Output is correct
48 Correct 320 ms 336832 KB Output is correct
49 Correct 318 ms 338856 KB Output is correct
50 Correct 224 ms 325348 KB Output is correct
51 Correct 229 ms 324364 KB Output is correct
52 Correct 309 ms 336440 KB Output is correct
53 Correct 311 ms 337476 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 324044 KB Output is correct
2 Correct 143 ms 321052 KB Output is correct
3 Correct 134 ms 303948 KB Output is correct
4 Correct 141 ms 303776 KB Output is correct
5 Correct 140 ms 314232 KB Output is correct
6 Correct 166 ms 314220 KB Output is correct
7 Correct 146 ms 314048 KB Output is correct
8 Correct 146 ms 313420 KB Output is correct
9 Correct 140 ms 313044 KB Output is correct
10 Correct 134 ms 303816 KB Output is correct
11 Correct 133 ms 303804 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 303732 KB Output is correct
2 Correct 133 ms 303776 KB Output is correct
3 Correct 141 ms 303948 KB Output is correct
4 Correct 144 ms 303996 KB Output is correct
5 Correct 143 ms 303824 KB Output is correct
6 Correct 135 ms 303780 KB Output is correct
7 Correct 593 ms 404592 KB Output is correct
8 Correct 1191 ms 511612 KB Output is correct
9 Correct 1210 ms 512548 KB Output is correct
10 Correct 1239 ms 512668 KB Output is correct
11 Correct 246 ms 358776 KB Output is correct
12 Correct 375 ms 411060 KB Output is correct
13 Correct 394 ms 414984 KB Output is correct

Subtask #7
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 303724 KB Output is correct
2 Correct 135 ms 304092 KB Output is correct
3 Correct 137 ms 304000 KB Output is correct
4 Correct 139 ms 304116 KB Output is correct
5 Correct 132 ms 303944 KB Output is correct
6 Correct 134 ms 303988 KB Output is correct
7 Correct 142 ms 304060 KB Output is correct
8 Correct 138 ms 304012 KB Output is correct
9 Correct 144 ms 304008 KB Output is correct
10 Correct 133 ms 303988 KB Output is correct
11 Correct 132 ms 304072 KB Output is correct
12 Correct 137 ms 304088 KB Output is correct
13 Correct 134 ms 303780 KB Output is correct
14 Correct 131 ms 303772 KB Output is correct
15 Correct 138 ms 303752 KB Output is correct
16 Correct 136 ms 303820 KB Output is correct
17 Correct 138 ms 304820 KB Output is correct
18 Correct 143 ms 304936 KB Output is correct
19 Correct 147 ms 304972 KB Output is correct
20 Correct 138 ms 304660 KB Output is correct
21 Correct 145 ms 304652 KB Output is correct
22 Correct 133 ms 304680 KB Output is correct
23 Correct 136 ms 304696 KB Output is correct
24 Correct 143 ms 304652 KB Output is correct
25 Correct 145 ms 308716 KB Output is correct
26 Correct 147 ms 308640 KB Output is correct
27 Correct 149 ms 308748 KB Output is correct
28 Correct 141 ms 306928 KB Output is correct
29 Correct 148 ms 307556 KB Output is correct
30 Correct 147 ms 307748 KB Output is correct
31 Correct 164 ms 307620 KB Output is correct
32 Correct 146 ms 307584 KB Output is correct
33 Correct 224 ms 335572 KB Output is correct
34 Correct 213 ms 330692 KB Output is correct
35 Correct 198 ms 330744 KB Output is correct
36 Correct 186 ms 326012 KB Output is correct
37 Correct 311 ms 350916 KB Output is correct
38 Correct 299 ms 350868 KB Output is correct
39 Correct 310 ms 351284 KB Output is correct
40 Correct 302 ms 348592 KB Output is correct
41 Correct 203 ms 325716 KB Output is correct
42 Correct 236 ms 328160 KB Output is correct
43 Correct 320 ms 336832 KB Output is correct
44 Correct 318 ms 338856 KB Output is correct
45 Correct 224 ms 325348 KB Output is correct
46 Correct 229 ms 324364 KB Output is correct
47 Correct 309 ms 336440 KB Output is correct
48 Correct 311 ms 337476 KB Output is correct
49 Correct 146 ms 324044 KB Output is correct
50 Correct 143 ms 321052 KB Output is correct
51 Correct 134 ms 303948 KB Output is correct
52 Correct 141 ms 303776 KB Output is correct
53 Correct 140 ms 314232 KB Output is correct
54 Correct 166 ms 314220 KB Output is correct
55 Correct 146 ms 314048 KB Output is correct
56 Correct 146 ms 313420 KB Output is correct
57 Correct 140 ms 313044 KB Output is correct
58 Correct 134 ms 303816 KB Output is correct
59 Correct 133 ms 303804 KB Output is correct
60 Correct 135 ms 303780 KB Output is correct
61 Correct 593 ms 404592 KB Output is correct
62 Correct 1191 ms 511612 KB Output is correct
63 Correct 1210 ms 512548 KB Output is correct
64 Correct 1239 ms 512668 KB Output is correct
65 Correct 246 ms 358776 KB Output is correct
66 Correct 375 ms 411060 KB Output is correct
67 Correct 394 ms 414984 KB Output is correct
68 Correct 147 ms 303732 KB Output is correct
69 Correct 133 ms 303776 KB Output is correct
70 Correct 141 ms 303948 KB Output is correct
71 Correct 144 ms 303996 KB Output is correct
72 Correct 143 ms 303824 KB Output is correct
73 Correct 1601 ms 645432 KB Output is correct
74 Correct 1383 ms 578120 KB Output is correct
75 Correct 1026 ms 577992 KB Output is correct
76 Correct 846 ms 511128 KB Output is correct
77 Correct 3014 ms 841612 KB Output is correct
78 Correct 1697 ms 526132 KB Output is correct
79 Correct 1742 ms 553572 KB Output is correct
80 Correct 2754 ms 656332 KB Output is correct
81 Correct 1760 ms 542592 KB Output is correct
82 Correct 2223 ms 617528 KB Output is correct
83 Correct 2896 ms 683452 KB Output is correct
84 Correct 1612 ms 522196 KB Output is correct
85 Correct 2800 ms 667236 KB Output is correct
86 Correct 2648 ms 656860 KB Output is correct
87 Correct 1751 ms 646200 KB Output is correct
88 Correct 3142 ms 830884 KB Output is correct
89 Correct 2939 ms 839892 KB Output is correct
90 Correct 3032 ms 840068 KB Output is correct