oj.uz

Submission #579585

# Submission time Handle Problem Language Result Execution time Memory
579585 2022-06-19T11:57:47 Z 2fat2code Rectangles (IOI19_rect) C++17
100 / 100
 2207 ms 577700 KB 
#include "rect.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 2505;

int n, m;
long long aib[nmax], ans;
vector<pair<int,int>>LE[nmax][nmax], UP[nmax][nmax];

void update(int pos, int val){
    for(int i=pos;i<nmax;i+=i&-i){
        aib[i] += val;
    }
}

long long query(int pos){
    long long rs = 0;
    for(int i=pos;i>=1;i-=i&-i){
        rs += aib[i];
    }
    return rs;
}

struct event{
    int latime, inaltime, tip;
    friend bool operator < (event A, event B){
        if(A.latime != B.latime){
            return A.latime < B.latime;
        }
        else{
            return A.tip < B.tip;
        }
    }
};

vector<event> O_o;

long long count_rectangles(vector<vector<int>> a) {
	n = a.size();
	m = a[0].size();
    for(int i=0;i<m;i++){
        vector<pair<int,int>> st;
        for(int j=0;j<n;j++){
            for(int t=((int)st.size())-2;t>=0;t--){
                if(st[t].fr > st[t+1].fr && a[j][i] > st[t+1].fr){
                    UP[j - 1][i].push_back({st[t].sc + 1, 1});
                }
                else if(st[t+1].fr > a[j][i]){
                    break;
                }
                st.pop_back();
            }
            if(j >= 1)reverse(all(UP[j - 1][i]));
            st.push_back({a[j][i], j});
        }
    }
    for(int i=0;i<n;i++){
        vector <pair<int,int>> st;
        for(int j=0;j<m;j++){
            for(int t=st.size()-2;t>=0;t--){
                if(st[t].fr > st[t+1].fr && a[i][j] > st[t+1].fr){
                    LE[i][j - 1].push_back({st[t].sc + 1, 1});
                }
                else if(st[t+1].fr > a[i][j]){
                    break;
                }
                st.pop_back();
            }
            if(j >= 1)reverse(all(LE[i][j - 1]));
            st.push_back({a[i][j], j});
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i > 0){
                for(auto &it : LE[i][j]){
                    auto it1 = lower_bound(all(LE[i-1][j]), it) - LE[i-1][j].begin();
                    if(it1 < LE[i-1][j].size() && LE[i-1][j][it1].fr == it.fr){
                        it.sc = LE[i-1][j][it1].sc + 1;
                    }
                }
            }
            if(j > 0){
                for(auto &it : UP[i][j]){
                    auto it1 = lower_bound(all(UP[i][j-1]), it) - UP[i][j-1].begin();
                    if(it1 < UP[i][j-1].size() && UP[i][j-1][it1].fr == it.fr){
                        it.sc = UP[i][j-1][it1].sc + 1;
                    }
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            O_o.clear();
            for(auto it : LE[i][j]){
                O_o.push_back({j - it.fr + 1, it.sc, 1});
            }
            for(auto it : UP[i][j]){
                O_o.push_back({it.sc, i - it.fr + 1, 2});
            }
            sort(all(O_o));
            for(auto it : O_o){
                if(it.tip == 1){
                    update(nmax - it.inaltime, 1);
                }
                else{
                    ans += query(nmax - it.inaltime);
                }
            }
            for(auto it : O_o){
                if(it.tip == 1){
                    update(nmax - it.inaltime, -1);
                }
            }
        }
    }
	return ans;
}


/**
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6

*/

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:83:28: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |                     if(it1 < LE[i-1][j].size() && LE[i-1][j][it1].fr == it.fr){
      |                        ~~~~^~~~~~~~~~~~~~~~~~~
rect.cpp:91:28: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                     if(it1 < UP[i][j-1].size() && UP[i][j-1][it1].fr == it.fr){
      |                        ~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 294952 KB Output is correct
2 Correct 146 ms 294988 KB Output is correct
3 Correct 133 ms 294956 KB Output is correct
4 Correct 142 ms 295016 KB Output is correct
5 Correct 139 ms 295008 KB Output is correct
6 Correct 139 ms 294988 KB Output is correct
7 Correct 149 ms 294988 KB Output is correct
8 Correct 149 ms 294928 KB Output is correct
9 Correct 146 ms 294932 KB Output is correct
10 Correct 144 ms 295028 KB Output is correct
11 Correct 153 ms 295052 KB Output is correct
12 Correct 142 ms 295004 KB Output is correct
13 Correct 142 ms 294892 KB Output is correct
14 Correct 150 ms 295012 KB Output is correct
15 Correct 162 ms 294992 KB Output is correct
16 Correct 149 ms 295004 KB Output is correct
17 Correct 149 ms 294888 KB Output is correct
18 Correct 146 ms 294988 KB Output is correct
19 Correct 147 ms 295000 KB Output is correct
20 Correct 147 ms 295004 KB Output is correct
21 Correct 156 ms 294968 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 294952 KB Output is correct
2 Correct 146 ms 294988 KB Output is correct
3 Correct 133 ms 294956 KB Output is correct
4 Correct 142 ms 295016 KB Output is correct
5 Correct 139 ms 295008 KB Output is correct
6 Correct 139 ms 294988 KB Output is correct
7 Correct 149 ms 294988 KB Output is correct
8 Correct 149 ms 294928 KB Output is correct
9 Correct 146 ms 294932 KB Output is correct
10 Correct 144 ms 295028 KB Output is correct
11 Correct 153 ms 295052 KB Output is correct
12 Correct 142 ms 295004 KB Output is correct
13 Correct 142 ms 294892 KB Output is correct
14 Correct 150 ms 295012 KB Output is correct
15 Correct 162 ms 294992 KB Output is correct
16 Correct 149 ms 295004 KB Output is correct
17 Correct 149 ms 294888 KB Output is correct
18 Correct 146 ms 294988 KB Output is correct
19 Correct 147 ms 295000 KB Output is correct
20 Correct 147 ms 295004 KB Output is correct
21 Correct 156 ms 294968 KB Output is correct
22 Correct 143 ms 295136 KB Output is correct
23 Correct 144 ms 295272 KB Output is correct
24 Correct 162 ms 295200 KB Output is correct
25 Correct 157 ms 295136 KB Output is correct
26 Correct 160 ms 295284 KB Output is correct
27 Correct 142 ms 295252 KB Output is correct
28 Correct 195 ms 295168 KB Output is correct
29 Correct 141 ms 295116 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 294952 KB Output is correct
2 Correct 146 ms 294988 KB Output is correct
3 Correct 133 ms 294956 KB Output is correct
4 Correct 142 ms 295016 KB Output is correct
5 Correct 139 ms 295008 KB Output is correct
6 Correct 139 ms 294988 KB Output is correct
7 Correct 149 ms 294988 KB Output is correct
8 Correct 149 ms 294928 KB Output is correct
9 Correct 146 ms 294932 KB Output is correct
10 Correct 144 ms 295028 KB Output is correct
11 Correct 153 ms 295052 KB Output is correct
12 Correct 142 ms 295004 KB Output is correct
13 Correct 142 ms 294892 KB Output is correct
14 Correct 150 ms 295012 KB Output is correct
15 Correct 162 ms 294992 KB Output is correct
16 Correct 149 ms 295004 KB Output is correct
17 Correct 143 ms 295136 KB Output is correct
18 Correct 144 ms 295272 KB Output is correct
19 Correct 162 ms 295200 KB Output is correct
20 Correct 157 ms 295136 KB Output is correct
21 Correct 160 ms 295284 KB Output is correct
22 Correct 142 ms 295252 KB Output is correct
23 Correct 195 ms 295168 KB Output is correct
24 Correct 141 ms 295116 KB Output is correct
25 Correct 149 ms 294888 KB Output is correct
26 Correct 146 ms 294988 KB Output is correct
27 Correct 147 ms 295000 KB Output is correct
28 Correct 147 ms 295004 KB Output is correct
29 Correct 156 ms 294968 KB Output is correct
30 Correct 164 ms 296360 KB Output is correct
31 Correct 162 ms 296328 KB Output is correct
32 Correct 151 ms 296424 KB Output is correct
33 Correct 140 ms 296112 KB Output is correct
34 Correct 147 ms 296884 KB Output is correct
35 Correct 160 ms 297156 KB Output is correct
36 Correct 155 ms 296852 KB Output is correct
37 Correct 146 ms 296892 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 294952 KB Output is correct
2 Correct 146 ms 294988 KB Output is correct
3 Correct 133 ms 294956 KB Output is correct
4 Correct 142 ms 295016 KB Output is correct
5 Correct 139 ms 295008 KB Output is correct
6 Correct 139 ms 294988 KB Output is correct
7 Correct 149 ms 294988 KB Output is correct
8 Correct 149 ms 294928 KB Output is correct
9 Correct 146 ms 294932 KB Output is correct
10 Correct 144 ms 295028 KB Output is correct
11 Correct 153 ms 295052 KB Output is correct
12 Correct 142 ms 295004 KB Output is correct
13 Correct 142 ms 294892 KB Output is correct
14 Correct 150 ms 295012 KB Output is correct
15 Correct 162 ms 294992 KB Output is correct
16 Correct 149 ms 295004 KB Output is correct
17 Correct 143 ms 295136 KB Output is correct
18 Correct 144 ms 295272 KB Output is correct
19 Correct 162 ms 295200 KB Output is correct
20 Correct 157 ms 295136 KB Output is correct
21 Correct 160 ms 295284 KB Output is correct
22 Correct 142 ms 295252 KB Output is correct
23 Correct 195 ms 295168 KB Output is correct
24 Correct 141 ms 295116 KB Output is correct
25 Correct 164 ms 296360 KB Output is correct
26 Correct 162 ms 296328 KB Output is correct
27 Correct 151 ms 296424 KB Output is correct
28 Correct 140 ms 296112 KB Output is correct
29 Correct 147 ms 296884 KB Output is correct
30 Correct 160 ms 297156 KB Output is correct
31 Correct 155 ms 296852 KB Output is correct
32 Correct 146 ms 296892 KB Output is correct
33 Correct 149 ms 294888 KB Output is correct
34 Correct 146 ms 294988 KB Output is correct
35 Correct 147 ms 295000 KB Output is correct
36 Correct 147 ms 295004 KB Output is correct
37 Correct 156 ms 294968 KB Output is correct
38 Correct 196 ms 306176 KB Output is correct
39 Correct 196 ms 310740 KB Output is correct
40 Correct 206 ms 310840 KB Output is correct
41 Correct 231 ms 315596 KB Output is correct
42 Correct 244 ms 311552 KB Output is correct
43 Correct 258 ms 311448 KB Output is correct
44 Correct 243 ms 311532 KB Output is correct
45 Correct 246 ms 310924 KB Output is correct
46 Correct 194 ms 307516 KB Output is correct
47 Correct 217 ms 310024 KB Output is correct
48 Correct 285 ms 318156 KB Output is correct
49 Correct 299 ms 318420 KB Output is correct
50 Correct 209 ms 307376 KB Output is correct
51 Correct 209 ms 307332 KB Output is correct
52 Correct 277 ms 316928 KB Output is correct
53 Correct 294 ms 317040 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 295372 KB Output is correct
2 Correct 137 ms 295224 KB Output is correct
3 Correct 136 ms 295028 KB Output is correct
4 Correct 140 ms 294908 KB Output is correct
5 Correct 147 ms 295228 KB Output is correct
6 Correct 132 ms 295256 KB Output is correct
7 Correct 135 ms 295164 KB Output is correct
8 Correct 135 ms 295204 KB Output is correct
9 Correct 139 ms 295244 KB Output is correct
10 Correct 135 ms 295072 KB Output is correct
11 Correct 134 ms 295040 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 294888 KB Output is correct
2 Correct 146 ms 294988 KB Output is correct
3 Correct 147 ms 295000 KB Output is correct
4 Correct 147 ms 295004 KB Output is correct
5 Correct 156 ms 294968 KB Output is correct
6 Correct 143 ms 294988 KB Output is correct
7 Correct 547 ms 363668 KB Output is correct
8 Correct 972 ms 443992 KB Output is correct
9 Correct 1037 ms 444588 KB Output is correct
10 Correct 1062 ms 444628 KB Output is correct
11 Correct 287 ms 320648 KB Output is correct
12 Correct 450 ms 344004 KB Output is correct
13 Correct 514 ms 347028 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 294952 KB Output is correct
2 Correct 146 ms 294988 KB Output is correct
3 Correct 133 ms 294956 KB Output is correct
4 Correct 142 ms 295016 KB Output is correct
5 Correct 139 ms 295008 KB Output is correct
6 Correct 139 ms 294988 KB Output is correct
7 Correct 149 ms 294988 KB Output is correct
8 Correct 149 ms 294928 KB Output is correct
9 Correct 146 ms 294932 KB Output is correct
10 Correct 144 ms 295028 KB Output is correct
11 Correct 153 ms 295052 KB Output is correct
12 Correct 142 ms 295004 KB Output is correct
13 Correct 142 ms 294892 KB Output is correct
14 Correct 150 ms 295012 KB Output is correct
15 Correct 162 ms 294992 KB Output is correct
16 Correct 149 ms 295004 KB Output is correct
17 Correct 143 ms 295136 KB Output is correct
18 Correct 144 ms 295272 KB Output is correct
19 Correct 162 ms 295200 KB Output is correct
20 Correct 157 ms 295136 KB Output is correct
21 Correct 160 ms 295284 KB Output is correct
22 Correct 142 ms 295252 KB Output is correct
23 Correct 195 ms 295168 KB Output is correct
24 Correct 141 ms 295116 KB Output is correct
25 Correct 164 ms 296360 KB Output is correct
26 Correct 162 ms 296328 KB Output is correct
27 Correct 151 ms 296424 KB Output is correct
28 Correct 140 ms 296112 KB Output is correct
29 Correct 147 ms 296884 KB Output is correct
30 Correct 160 ms 297156 KB Output is correct
31 Correct 155 ms 296852 KB Output is correct
32 Correct 146 ms 296892 KB Output is correct
33 Correct 196 ms 306176 KB Output is correct
34 Correct 196 ms 310740 KB Output is correct
35 Correct 206 ms 310840 KB Output is correct
36 Correct 231 ms 315596 KB Output is correct
37 Correct 244 ms 311552 KB Output is correct
38 Correct 258 ms 311448 KB Output is correct
39 Correct 243 ms 311532 KB Output is correct
40 Correct 246 ms 310924 KB Output is correct
41 Correct 194 ms 307516 KB Output is correct
42 Correct 217 ms 310024 KB Output is correct
43 Correct 285 ms 318156 KB Output is correct
44 Correct 299 ms 318420 KB Output is correct
45 Correct 209 ms 307376 KB Output is correct
46 Correct 209 ms 307332 KB Output is correct
47 Correct 277 ms 316928 KB Output is correct
48 Correct 294 ms 317040 KB Output is correct
49 Correct 154 ms 295372 KB Output is correct
50 Correct 137 ms 295224 KB Output is correct
51 Correct 136 ms 295028 KB Output is correct
52 Correct 140 ms 294908 KB Output is correct
53 Correct 147 ms 295228 KB Output is correct
54 Correct 132 ms 295256 KB Output is correct
55 Correct 135 ms 295164 KB Output is correct
56 Correct 135 ms 295204 KB Output is correct
57 Correct 139 ms 295244 KB Output is correct
58 Correct 135 ms 295072 KB Output is correct
59 Correct 134 ms 295040 KB Output is correct
60 Correct 143 ms 294988 KB Output is correct
61 Correct 547 ms 363668 KB Output is correct
62 Correct 972 ms 443992 KB Output is correct
63 Correct 1037 ms 444588 KB Output is correct
64 Correct 1062 ms 444628 KB Output is correct
65 Correct 287 ms 320648 KB Output is correct
66 Correct 450 ms 344004 KB Output is correct
67 Correct 514 ms 347028 KB Output is correct
68 Correct 149 ms 294888 KB Output is correct
69 Correct 146 ms 294988 KB Output is correct
70 Correct 147 ms 295000 KB Output is correct
71 Correct 147 ms 295004 KB Output is correct
72 Correct 156 ms 294968 KB Output is correct
73 Correct 887 ms 407212 KB Output is correct
74 Correct 991 ms 473984 KB Output is correct
75 Correct 1307 ms 474172 KB Output is correct
76 Correct 1295 ms 540784 KB Output is correct
77 Correct 1802 ms 463276 KB Output is correct
78 Correct 1287 ms 464404 KB Output is correct
79 Correct 1392 ms 473500 KB Output is correct
80 Correct 2187 ms 575496 KB Output is correct
81 Correct 1364 ms 464704 KB Output is correct
82 Correct 1702 ms 521232 KB Output is correct
83 Correct 2207 ms 577700 KB Output is correct
84 Correct 1281 ms 454180 KB Output is correct
85 Correct 2170 ms 561408 KB Output is correct
86 Correct 2111 ms 553068 KB Output is correct
87 Correct 1073 ms 399776 KB Output is correct
88 Correct 1790 ms 462552 KB Output is correct
89 Correct 1733 ms 462280 KB Output is correct
90 Correct 1718 ms 462248 KB Output is correct