oj.uz

답안 #160942

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160942 2019-10-30T16:32:25 Z georgerapeanu Rectangles (IOI19_rect) C++14
100 / 100
 3771 ms 552964 KB 
#include "rect.h"

#pragma once
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int aib[2505][2505];
int n,m;
void update_aib(int x,int y,int val){
    x++;
    y++;
    for(int i = x;i;i -= (-i) & i){
        for(int j = y;j;j -= (-j) & j){
            aib[i][j] += val;
        }
    }
}

int query_aib(int x,int y){
    x++;
    y++;
    int ans = 0;
    for(int i = x;i <= m;i += (-i) & i){
        for(int j = y;j <= n;j += (-j) & j){
            ans += aib[i][j];
        }
    }
    return ans;
}


int lst = 0;
void reset_calc(){
    lst = 0;
}

int calc(int l,int r,vector<pair<pair<int,int>,int> > &v){
    while(lst < (int)v.size() && v[lst].first.first > l){
        lst++;
    }
    if(lst != (int)v.size() && v[lst].first == make_pair(l,r)){
        return 1 + v[lst].second;
    }
    return 1;
}

long long count_rectangles(std::vector<std::vector<int> > a) {

    vector<pair<pair<int,int>,int> > v_heights;
    vector<pair<pair<int,int>,int> > tmp;

    n = a.size();
    m = a[0].size();

    long long ans = 0;

    vector<vector<int> > v_stack(m,vector<int>(0));
    vector<vector<vector<pair<pair<int,int>,int> > > > tervals(n,vector<vector<pair<pair<int,int>,int> > >(m,vector<pair<pair<int,int>,int> >(0)));
    for(int i = 0;i < n;i++){
        vector<int> h_stack;
        v_heights.clear();
        for(int j = 0;j < m;j++){
            tmp.clear();
            reset_calc();
            while(v_stack[j].size() > 0 && a[v_stack[j].back()][j] < a[i][j]){
                tmp.push_back({{v_stack[j].back(),i},calc(v_stack[j].back(),i,v_heights)});
                v_stack[j].pop_back();
            }
            if(v_stack[j].size() > 0){
                tmp.push_back({{v_stack[j].back(),i},calc(v_stack[j].back(),i,v_heights)});
            }
            while(v_stack[j].size() > 0 && a[v_stack[j].back()][j] <= a[i][j]){
                v_stack[j].pop_back();
            }
            v_stack[j].push_back(i);
            v_heights = tmp;
            if(i > 0 && j < m - 1){
                for(auto it:tervals[i - 1][j + 1]){
                    if(it.first.first == j){
                        continue;
                    }
                    update_aib(it.first.first,it.second,1);
                }

                for(auto it:v_heights){
                    if(it.first.first == it.first.second - 1){
                        continue;
                    }
                    ans += query_aib(max(0,j - it.second),it.first.second - it.first.first - 1);
                }
                
                for(auto it:tervals[i - 1][j + 1]){
                    if(it.first.first == j){
                        continue;
                    }
                    update_aib(it.first.first,it.second,-1);
                }
            }
        }
        for(int j = 0;j < m;j++){
            reset_calc();
            while(h_stack.size() > 0 && a[i][h_stack.back()] < a[i][j]){
                if(i > 0){
                    tervals[i][j].push_back({{h_stack.back(),j},calc(h_stack.back(),j,tervals[i - 1][j])});
                }
                else{
                    tervals[i][j].push_back({{h_stack.back(),j},1});
                }
                h_stack.pop_back();
            }
            if(h_stack.size() > 0){
                if(i > 0){
                    tervals[i][j].push_back({{h_stack.back(),j},calc(h_stack.back(),j,tervals[i - 1][j])});
                }
                else{
                    tervals[i][j].push_back({{h_stack.back(),j},1});
                }
            }
            while(h_stack.size() > 0 && a[i][h_stack.back()] <= a[i][j]){
                h_stack.pop_back();
            }
            h_stack.push_back(j);
        }
    }

	return ans;
}

Compilation message

rect.cpp:3:9: warning: #pragma once in main file
 #pragma once
         ^~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 476 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 504 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 476 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 4 ms 1276 KB Output is correct
18 Correct 4 ms 1272 KB Output is correct
19 Correct 4 ms 1272 KB Output is correct
20 Correct 4 ms 1016 KB Output is correct
21 Correct 5 ms 1144 KB Output is correct
22 Correct 5 ms 1144 KB Output is correct
23 Correct 5 ms 1144 KB Output is correct
24 Correct 3 ms 632 KB Output is correct
25 Correct 2 ms 256 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 504 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 476 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 4 ms 1276 KB Output is correct
18 Correct 4 ms 1272 KB Output is correct
19 Correct 4 ms 1272 KB Output is correct
20 Correct 4 ms 1016 KB Output is correct
21 Correct 5 ms 1144 KB Output is correct
22 Correct 5 ms 1144 KB Output is correct
23 Correct 5 ms 1144 KB Output is correct
24 Correct 3 ms 632 KB Output is correct
25 Correct 17 ms 4856 KB Output is correct
26 Correct 17 ms 4856 KB Output is correct
27 Correct 17 ms 4984 KB Output is correct
28 Correct 14 ms 3704 KB Output is correct
29 Correct 20 ms 4216 KB Output is correct
30 Correct 20 ms 4332 KB Output is correct
31 Correct 20 ms 4344 KB Output is correct
32 Correct 19 ms 4344 KB Output is correct
33 Correct 2 ms 256 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 504 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 2 ms 376 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 476 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 4 ms 1276 KB Output is correct
18 Correct 4 ms 1272 KB Output is correct
19 Correct 4 ms 1272 KB Output is correct
20 Correct 4 ms 1016 KB Output is correct
21 Correct 5 ms 1144 KB Output is correct
22 Correct 5 ms 1144 KB Output is correct
23 Correct 5 ms 1144 KB Output is correct
24 Correct 3 ms 632 KB Output is correct
25 Correct 17 ms 4856 KB Output is correct
26 Correct 17 ms 4856 KB Output is correct
27 Correct 17 ms 4984 KB Output is correct
28 Correct 14 ms 3704 KB Output is correct
29 Correct 20 ms 4216 KB Output is correct
30 Correct 20 ms 4332 KB Output is correct
31 Correct 20 ms 4344 KB Output is correct
32 Correct 19 ms 4344 KB Output is correct
33 Correct 135 ms 40964 KB Output is correct
34 Correct 141 ms 36864 KB Output is correct
35 Correct 148 ms 40956 KB Output is correct
36 Correct 151 ms 36808 KB Output is correct
37 Correct 218 ms 48596 KB Output is correct
38 Correct 218 ms 48504 KB Output is correct
39 Correct 217 ms 48356 KB Output is correct
40 Correct 273 ms 45816 KB Output is correct
41 Correct 131 ms 34808 KB Output is correct
42 Correct 157 ms 35636 KB Output is correct
43 Correct 238 ms 40744 KB Output is correct
44 Correct 256 ms 40696 KB Output is correct
45 Correct 124 ms 21240 KB Output is correct
46 Correct 126 ms 22904 KB Output is correct
47 Correct 235 ms 40540 KB Output is correct
48 Correct 248 ms 40384 KB Output is correct
49 Correct 2 ms 256 KB Output is correct
50 Correct 2 ms 376 KB Output is correct
51 Correct 2 ms 504 KB Output is correct
52 Correct 2 ms 376 KB Output is correct
53 Correct 2 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11128 KB Output is correct
2 Correct 10 ms 9592 KB Output is correct
3 Correct 3 ms 892 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 12 ms 9848 KB Output is correct
6 Correct 12 ms 9720 KB Output is correct
7 Correct 11 ms 9852 KB Output is correct
8 Correct 11 ms 9464 KB Output is correct
9 Correct 11 ms 9464 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 9 ms 8056 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 782 ms 192180 KB Output is correct
3 Correct 1721 ms 400212 KB Output is correct
4 Correct 1753 ms 414432 KB Output is correct
5 Correct 1737 ms 413248 KB Output is correct
6 Correct 532 ms 199772 KB Output is correct
7 Correct 1004 ms 379384 KB Output is correct
8 Correct 1058 ms 404260 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct

Subtask #7
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 476 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 4 ms 1276 KB Output is correct
18 Correct 4 ms 1272 KB Output is correct
19 Correct 4 ms 1272 KB Output is correct
20 Correct 4 ms 1016 KB Output is correct
21 Correct 5 ms 1144 KB Output is correct
22 Correct 5 ms 1144 KB Output is correct
23 Correct 5 ms 1144 KB Output is correct
24 Correct 3 ms 632 KB Output is correct
25 Correct 17 ms 4856 KB Output is correct
26 Correct 17 ms 4856 KB Output is correct
27 Correct 17 ms 4984 KB Output is correct
28 Correct 14 ms 3704 KB Output is correct
29 Correct 20 ms 4216 KB Output is correct
30 Correct 20 ms 4332 KB Output is correct
31 Correct 20 ms 4344 KB Output is correct
32 Correct 19 ms 4344 KB Output is correct
33 Correct 135 ms 40964 KB Output is correct
34 Correct 141 ms 36864 KB Output is correct
35 Correct 148 ms 40956 KB Output is correct
36 Correct 151 ms 36808 KB Output is correct
37 Correct 218 ms 48596 KB Output is correct
38 Correct 218 ms 48504 KB Output is correct
39 Correct 217 ms 48356 KB Output is correct
40 Correct 273 ms 45816 KB Output is correct
41 Correct 131 ms 34808 KB Output is correct
42 Correct 157 ms 35636 KB Output is correct
43 Correct 238 ms 40744 KB Output is correct
44 Correct 256 ms 40696 KB Output is correct
45 Correct 124 ms 21240 KB Output is correct
46 Correct 126 ms 22904 KB Output is correct
47 Correct 235 ms 40540 KB Output is correct
48 Correct 248 ms 40384 KB Output is correct
49 Correct 12 ms 11128 KB Output is correct
50 Correct 10 ms 9592 KB Output is correct
51 Correct 3 ms 892 KB Output is correct
52 Correct 2 ms 256 KB Output is correct
53 Correct 12 ms 9848 KB Output is correct
54 Correct 12 ms 9720 KB Output is correct
55 Correct 11 ms 9852 KB Output is correct
56 Correct 11 ms 9464 KB Output is correct
57 Correct 11 ms 9464 KB Output is correct
58 Correct 3 ms 632 KB Output is correct
59 Correct 9 ms 8056 KB Output is correct
60 Correct 2 ms 376 KB Output is correct
61 Correct 782 ms 192180 KB Output is correct
62 Correct 1721 ms 400212 KB Output is correct
63 Correct 1753 ms 414432 KB Output is correct
64 Correct 1737 ms 413248 KB Output is correct
65 Correct 532 ms 199772 KB Output is correct
66 Correct 1004 ms 379384 KB Output is correct
67 Correct 1058 ms 404260 KB Output is correct
68 Correct 1932 ms 463944 KB Output is correct
69 Correct 1962 ms 466792 KB Output is correct
70 Correct 2054 ms 463932 KB Output is correct
71 Correct 2130 ms 466636 KB Output is correct
72 Correct 3420 ms 537852 KB Output is correct
73 Correct 2057 ms 299936 KB Output is correct
74 Correct 2154 ms 319804 KB Output is correct
75 Correct 3551 ms 492676 KB Output is correct
76 Correct 2228 ms 316008 KB Output is correct
77 Correct 2807 ms 415692 KB Output is correct
78 Correct 3771 ms 471528 KB Output is correct
79 Correct 1910 ms 306424 KB Output is correct
80 Correct 3347 ms 467844 KB Output is correct
81 Correct 3201 ms 484896 KB Output is correct
82 Correct 1974 ms 355828 KB Output is correct
83 Correct 3462 ms 537432 KB Output is correct
84 Correct 3435 ms 546120 KB Output is correct
85 Correct 3426 ms 552964 KB Output is correct
86 Correct 2 ms 256 KB Output is correct
87 Correct 2 ms 376 KB Output is correct
88 Correct 2 ms 504 KB Output is correct
89 Correct 2 ms 376 KB Output is correct
90 Correct 2 ms 376 KB Output is correct