oj.uz

Submission #415498

# Submission time Handle Problem Language Result Execution time Memory
415498 2021-06-01T07:34:58 Z qwerasdfzxcl Rectangles (IOI19_rect) C++14
100 / 100
 4968 ms 442684 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

typedef long long ll;
using namespace std;
vector<int> pos[2525][2525];
int n, M;
int curpossum[2525], curmax[2525];
vector<int> cur2[2525], tmp[2525];

ll div1(int s, int e, vector<vector<int>> &matrix){
    if (e-s==1){
        if (matrix[1][s]<matrix[1][s+1] && matrix[1][s]<matrix[1][s-1]) return 1;
        return 0;
    }
    ll ret=div1(s, (s+e)/2, matrix)+div1((s+e)/2, e, matrix);
    int x=(s+e)/2-1, y=(s+e)/2, cur;
    cur=max(matrix[1][x], matrix[1][y]);
    while(x>s && y<e-1){
        if (cur<matrix[1][x-1] && cur<matrix[1][y+1]) ret++;
        if (matrix[1][x-1]<matrix[1][y+1]) cur=max(cur, matrix[1][--x]);
        else cur=max(cur, matrix[1][++y]);
    }
    if (x==s){
        for (;y<=e-1;cur=max(cur, matrix[1][++y])) if(cur<matrix[1][x-1] && cur<matrix[1][y+1]) ret++;
    }
    else{
        for (;x>=s;cur=max(cur, matrix[1][--x])) if(cur<matrix[1][x-1] && cur<matrix[1][y+1]) ret++;
    }
    return ret;
}

ll div1idxrev(int s, int e, int idx, vector<vector<int>> &matrix){
    if (e-s==1){
        if (matrix[s][idx]<matrix[s+1][idx] && matrix[s][idx]<matrix[s-1][idx] && matrix[s][idx]<min(matrix[s][idx-1], matrix[s][idx+1])) return 1;
        return 0;
    }
    ll ret=div1idxrev(s, (s+e)/2, idx, matrix)+div1idxrev((s+e)/2, e, idx, matrix);
    int x=(s+e)/2-1, y=(s+e)/2, cur;
    cur=max(matrix[x][idx], matrix[y][idx]);
    bool tmp1=(matrix[x][idx]<min(matrix[x][idx-1], matrix[x][idx+1]))&&(matrix[y][idx]<min(matrix[y][idx-1], matrix[y][idx+1]));
    while(x>s && y<e-1){
        if (!tmp1) return ret;
        if (cur<matrix[x-1][idx] && cur<matrix[y+1][idx]) ret++;
        if (matrix[x-1][idx]<matrix[y+1][idx]){
            cur=max(cur, matrix[--x][idx]);
            tmp1=matrix[x][idx]<min(matrix[x][idx-1], matrix[x][idx+1]);
        }
        else{
            cur=max(cur, matrix[++y][idx]);
            tmp1=matrix[y][idx]<min(matrix[y][idx-1], matrix[y][idx+1]);
        }
    }
    if (x==s){
        for (;y<=e-1;cur=max(cur, matrix[y][idx])){
            if (!tmp1) return ret;
            if(cur<matrix[x-1][idx] && cur<matrix[y+1][idx]) ret++;
            y++;
            tmp1=matrix[y][idx]<min(matrix[y][idx-1], matrix[y][idx+1]);
        }
    }
    else{
        for (;x>=s;cur=max(cur, matrix[x][idx])){
            if (!tmp1) return ret;
            if(cur<matrix[x-1][idx] && cur<matrix[y+1][idx]) ret++;
            x--;
            tmp1=matrix[x][idx]<min(matrix[x][idx-1], matrix[x][idx+1]);
        }
    }
    return ret;
}

ll div3(int s, int e, int s0, int e0, vector<vector<int>> &matrix){
    int m=(s+e)/2, m0=(s0+e0)/2;
    curpossum[s]=0;
    int x1=m-1, x2=m;
    if (e-s==1){
        ll ret=0;
        for (int i=s0;i<e0;i++){
            if (matrix[s][i]<matrix[s-1][i] && matrix[s][i]<matrix[s+1][i]){
                curpossum[i+1]=curpossum[i]+1;
            }
            else curpossum[i+1]=curpossum[i];
        }
        for (int i=s0;i<m0;i++){
            for (int &j:pos[s][i]){
                if (curpossum[j+1]-curpossum[i]==(j+1-i)) ret++;
            }
        }
        return ret;
    }
    ll ret=div3(s, m, s0, e0, matrix)+div3(m, e, s0, e0, matrix);
    for (register int i=s0;i<e0;i++){
        curmax[i]=max(matrix[x1][i], matrix[x2][i]);
        if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
            curpossum[i+1]=curpossum[i]+1;
        }
        else{
            curpossum[i+1]=curpossum[i];
        }
    }
    bool test=0;
    for (register int i=s0;i<m0;i++){
        cur2[i].clear();
        tmp[i].clear();
        register int j1=0, j2=0, sz1=pos[x1][i].size(), sz2=pos[x2][i].size();
        while(j1<sz1 && j2<sz2){
            if (pos[x1][i][j1]==pos[x2][i][j2]){
                cur2[i].push_back(pos[x1][i][j1]);
                test=1;
                if (curpossum[cur2[i].back()+1]-curpossum[i]==(cur2[i].back()-i+1)){
                    ret++;
                }
                j1++, j2++;
            }
            else if (pos[x1][i][j1]<pos[x2][i][j2]) j1++;
            else j2++;
        }
    }
    if (!test) return ret;
    while(x1>s && x2<e-1){
        if (!test) return ret;
        test=0;
        if (matrix[x1-1][m0]<matrix[x2+1][m0] || (matrix[x1-1][m0]==matrix[x2+1][m0] && matrix[x1-1][m0-1]<matrix[x2+1][m0-1])){
            x1--;
            for (register int i=s0;i<e0;i++){
                curmax[i]=max(curmax[i], matrix[x1][i]);
                if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
                    curpossum[i+1]=curpossum[i]+1;
                }
                else{
                    curpossum[i+1]=curpossum[i];
                }
            }
            for (register int i=s0;i<m0;i++){
                tmp[i].clear();
                register int j1=0, j2=0, sz1=cur2[i].size(), sz2=pos[x1][i].size();
                while(j1<sz1 && j2<sz2){
                    if (cur2[i][j1]==pos[x1][i][j2]){
                        test=1;
                        tmp[i].push_back(cur2[i][j1]);
                        if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
                        j1++, j2++;
                    }
                    else if (cur2[i][j1]<pos[x1][i][j2]) j1++;
                    else j2++;
                }
                swap(tmp[i], cur2[i]);
            }
        }
        else{
            x2++;
            for (register int i=s0;i<e0;i++){
                curmax[i]=max(curmax[i], matrix[x2][i]);
                if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
                    curpossum[i+1]=curpossum[i]+1;
                }
                else{
                    curpossum[i+1]=curpossum[i];
                }
            }
            for (register int i=s0;i<m0;i++){
                tmp[i].clear();
                register int j1=0, j2=0, sz1=cur2[i].size(), sz2=pos[x2][i].size();
                while(j1<sz1 && j2<sz2){
                    if (cur2[i][j1]==pos[x2][i][j2]){
                        test=1;
                        tmp[i].push_back(cur2[i][j1]);
                        if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
                        j1++, j2++;
                    }
                    else if (cur2[i][j1]<pos[x2][i][j2]) j1++;
                    else j2++;
                }
                swap(tmp[i], cur2[i]);
            }
        }
    }
    if (x1==s){
        x2++;
        for (;x2<=e-1;x2++){
            if (!test) return ret;
            test=0;
            for (register int i=s0;i<e0;i++){
                curmax[i]=max(curmax[i], matrix[x2][i]);
                if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
                    curpossum[i+1]=curpossum[i]+1;
                }
                else{
                    curpossum[i+1]=curpossum[i];
                }
            }
            for (register int i=s0;i<m0;i++){
                tmp[i].clear();
                register int j1=0, j2=0, sz1=cur2[i].size(), sz2=pos[x2][i].size();
                while(j1<sz1 && j2<sz2){
                    if (cur2[i][j1]==pos[x2][i][j2]){
                        test=1;
                        tmp[i].push_back(cur2[i][j1]);
                        if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
                        j1++, j2++;
                    }
                    else if (cur2[i][j1]<pos[x2][i][j2]) j1++;
                    else j2++;
                }
                swap(tmp[i], cur2[i]);
            }
        }
    }
    else{
        x1--;
        for (;x1>=s;x1--){
            if (!test) return ret;
            for (register int i=s0;i<e0;i++){
                curmax[i]=max(curmax[i], matrix[x1][i]);
                if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
                    curpossum[i+1]=curpossum[i]+1;
                }
                else{
                    curpossum[i+1]=curpossum[i];
                }
            }
            for (register int i=s0;i<m0;i++){
                tmp[i].clear();
                register int j1=0, j2=0, sz1=cur2[i].size(), sz2=pos[x1][i].size();
                while(j1<sz1 && j2<sz2){
                    if (cur2[i][j1]==pos[x1][i][j2]){
                        test=1;
                        tmp[i].push_back(cur2[i][j1]);
                        if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
                        j1++, j2++;
                    }
                    else if (cur2[i][j1]<pos[x1][i][j2]) j1++;
                    else j2++;
                }
                swap(tmp[i], cur2[i]);
            }
        }
    }
    return ret;
}

ll div2(int s, int e, vector<vector<int>> &matrix){
    if (e-s==1){
        return div1idxrev(1, n-1, s, matrix);
    }
    int m=(s+e)/2;
    ll ret=div2(s, m, matrix)+div2(m, e, matrix);
    for (register int i=0;i<n;i++){
        for (register int j=s;j<m;j++) pos[i][j].clear();
        register int x1=m-1, x2=m, cur1=max(matrix[i][x1], matrix[i][x2]);
        while(x1>s && x2<e-1){
            if (cur1<matrix[i][x1-1] && cur1<matrix[i][x2+1]) pos[i][x1].push_back(x2);
            if (matrix[i][x1-1]<matrix[i][x2+1]) cur1=max(cur1, matrix[i][--x1]);
            else cur1=max(cur1, matrix[i][++x2]);
        }
        if (x1==s){
            for (;x2<=e-1;cur1=max(cur1, matrix[i][++x2])) if (cur1<matrix[i][x1-1] && cur1<matrix[i][x2+1]) pos[i][x1].push_back(x2);
        }
        else{
            for (;x1>=s;cur1=max(cur1, matrix[i][--x1])) if (cur1<matrix[i][x1-1] && cur1<matrix[i][x2+1]) pos[i][x1].push_back(x2);
        }
    }
    ret += div3(1, n-1, s, e, matrix);
    return ret;
}

ll solve1(vector<vector<int>> &matrix){
    if (n<=2){
        return 0;
    }
    vector<pair<int, int>> pi;
    int s=-2;
    for (int i=0;i<M;i++) if (!(matrix[1][i]<matrix[0][i] && matrix[1][i]<matrix[2][i])){
        if (s==-2){
            s=i+1; continue;
        }
        if (s!=i) pi.push_back(make_pair(s, i));
        s=i+1;
    }
    ll ret=0;
    for (auto p:pi) ret += div1(p.first, p.second, matrix);
    return ret;
}

ll count_rectangles(vector<vector<int>> matrix){
  	n=matrix.size(), M=matrix[0].size();
    if (n<=3) return solve1(matrix);
    else if (M<=2) return 0;
    return div2(1, M-1, matrix);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 150064 KB Output is correct
2 Correct 93 ms 150084 KB Output is correct
3 Correct 94 ms 150100 KB Output is correct
4 Correct 103 ms 150088 KB Output is correct
5 Correct 92 ms 150128 KB Output is correct
6 Correct 104 ms 150172 KB Output is correct
7 Correct 108 ms 150088 KB Output is correct
8 Correct 93 ms 150108 KB Output is correct
9 Correct 94 ms 150024 KB Output is correct
10 Correct 90 ms 150116 KB Output is correct
11 Correct 103 ms 150084 KB Output is correct
12 Correct 92 ms 150084 KB Output is correct
13 Correct 98 ms 150048 KB Output is correct
14 Correct 93 ms 150124 KB Output is correct
15 Correct 92 ms 150080 KB Output is correct
16 Correct 90 ms 150144 KB Output is correct
17 Correct 91 ms 150080 KB Output is correct
18 Correct 108 ms 150048 KB Output is correct
19 Correct 92 ms 150120 KB Output is correct
20 Correct 109 ms 150076 KB Output is correct
21 Correct 91 ms 150084 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 150064 KB Output is correct
2 Correct 93 ms 150084 KB Output is correct
3 Correct 94 ms 150100 KB Output is correct
4 Correct 103 ms 150088 KB Output is correct
5 Correct 92 ms 150128 KB Output is correct
6 Correct 104 ms 150172 KB Output is correct
7 Correct 108 ms 150088 KB Output is correct
8 Correct 93 ms 150108 KB Output is correct
9 Correct 94 ms 150024 KB Output is correct
10 Correct 90 ms 150116 KB Output is correct
11 Correct 103 ms 150084 KB Output is correct
12 Correct 92 ms 150084 KB Output is correct
13 Correct 98 ms 150048 KB Output is correct
14 Correct 93 ms 150124 KB Output is correct
15 Correct 92 ms 150080 KB Output is correct
16 Correct 90 ms 150144 KB Output is correct
17 Correct 91 ms 150080 KB Output is correct
18 Correct 108 ms 150048 KB Output is correct
19 Correct 92 ms 150120 KB Output is correct
20 Correct 109 ms 150076 KB Output is correct
21 Correct 91 ms 150084 KB Output is correct
22 Correct 108 ms 150340 KB Output is correct
23 Correct 111 ms 150340 KB Output is correct
24 Correct 110 ms 150316 KB Output is correct
25 Correct 93 ms 150140 KB Output is correct
26 Correct 108 ms 150212 KB Output is correct
27 Correct 92 ms 150208 KB Output is correct
28 Correct 109 ms 150208 KB Output is correct
29 Correct 93 ms 150212 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 150064 KB Output is correct
2 Correct 93 ms 150084 KB Output is correct
3 Correct 94 ms 150100 KB Output is correct
4 Correct 103 ms 150088 KB Output is correct
5 Correct 92 ms 150128 KB Output is correct
6 Correct 104 ms 150172 KB Output is correct
7 Correct 108 ms 150088 KB Output is correct
8 Correct 93 ms 150108 KB Output is correct
9 Correct 94 ms 150024 KB Output is correct
10 Correct 90 ms 150116 KB Output is correct
11 Correct 103 ms 150084 KB Output is correct
12 Correct 92 ms 150084 KB Output is correct
13 Correct 98 ms 150048 KB Output is correct
14 Correct 93 ms 150124 KB Output is correct
15 Correct 92 ms 150080 KB Output is correct
16 Correct 90 ms 150144 KB Output is correct
17 Correct 108 ms 150340 KB Output is correct
18 Correct 111 ms 150340 KB Output is correct
19 Correct 110 ms 150316 KB Output is correct
20 Correct 93 ms 150140 KB Output is correct
21 Correct 108 ms 150212 KB Output is correct
22 Correct 92 ms 150208 KB Output is correct
23 Correct 109 ms 150208 KB Output is correct
24 Correct 93 ms 150212 KB Output is correct
25 Correct 91 ms 150080 KB Output is correct
26 Correct 108 ms 150048 KB Output is correct
27 Correct 92 ms 150120 KB Output is correct
28 Correct 109 ms 150076 KB Output is correct
29 Correct 91 ms 150084 KB Output is correct
30 Correct 104 ms 151924 KB Output is correct
31 Correct 109 ms 151876 KB Output is correct
32 Correct 107 ms 151936 KB Output is correct
33 Correct 121 ms 150672 KB Output is correct
34 Correct 117 ms 151064 KB Output is correct
35 Correct 108 ms 151076 KB Output is correct
36 Correct 126 ms 151084 KB Output is correct
37 Correct 116 ms 151108 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 150064 KB Output is correct
2 Correct 93 ms 150084 KB Output is correct
3 Correct 94 ms 150100 KB Output is correct
4 Correct 103 ms 150088 KB Output is correct
5 Correct 92 ms 150128 KB Output is correct
6 Correct 104 ms 150172 KB Output is correct
7 Correct 108 ms 150088 KB Output is correct
8 Correct 93 ms 150108 KB Output is correct
9 Correct 94 ms 150024 KB Output is correct
10 Correct 90 ms 150116 KB Output is correct
11 Correct 103 ms 150084 KB Output is correct
12 Correct 92 ms 150084 KB Output is correct
13 Correct 98 ms 150048 KB Output is correct
14 Correct 93 ms 150124 KB Output is correct
15 Correct 92 ms 150080 KB Output is correct
16 Correct 90 ms 150144 KB Output is correct
17 Correct 108 ms 150340 KB Output is correct
18 Correct 111 ms 150340 KB Output is correct
19 Correct 110 ms 150316 KB Output is correct
20 Correct 93 ms 150140 KB Output is correct
21 Correct 108 ms 150212 KB Output is correct
22 Correct 92 ms 150208 KB Output is correct
23 Correct 109 ms 150208 KB Output is correct
24 Correct 93 ms 150212 KB Output is correct
25 Correct 104 ms 151924 KB Output is correct
26 Correct 109 ms 151876 KB Output is correct
27 Correct 107 ms 151936 KB Output is correct
28 Correct 121 ms 150672 KB Output is correct
29 Correct 117 ms 151064 KB Output is correct
30 Correct 108 ms 151076 KB Output is correct
31 Correct 126 ms 151084 KB Output is correct
32 Correct 116 ms 151108 KB Output is correct
33 Correct 91 ms 150080 KB Output is correct
34 Correct 108 ms 150048 KB Output is correct
35 Correct 92 ms 150120 KB Output is correct
36 Correct 109 ms 150076 KB Output is correct
37 Correct 91 ms 150084 KB Output is correct
38 Correct 229 ms 164768 KB Output is correct
39 Correct 218 ms 158128 KB Output is correct
40 Correct 224 ms 164788 KB Output is correct
41 Correct 222 ms 158068 KB Output is correct
42 Correct 306 ms 172608 KB Output is correct
43 Correct 297 ms 172528 KB Output is correct
44 Correct 316 ms 172888 KB Output is correct
45 Correct 280 ms 171568 KB Output is correct
46 Correct 248 ms 156836 KB Output is correct
47 Correct 246 ms 157736 KB Output is correct
48 Correct 318 ms 160808 KB Output is correct
49 Correct 319 ms 162872 KB Output is correct
50 Correct 213 ms 156412 KB Output is correct
51 Correct 221 ms 156580 KB Output is correct
52 Correct 367 ms 161536 KB Output is correct
53 Correct 362 ms 162468 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 150260 KB Output is correct
2 Correct 91 ms 150216 KB Output is correct
3 Correct 90 ms 150088 KB Output is correct
4 Correct 95 ms 150112 KB Output is correct
5 Correct 110 ms 150240 KB Output is correct
6 Correct 93 ms 150152 KB Output is correct
7 Correct 91 ms 150196 KB Output is correct
8 Correct 107 ms 150220 KB Output is correct
9 Correct 93 ms 150160 KB Output is correct
10 Correct 107 ms 150124 KB Output is correct
11 Correct 112 ms 150148 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 150080 KB Output is correct
2 Correct 108 ms 150048 KB Output is correct
3 Correct 92 ms 150120 KB Output is correct
4 Correct 109 ms 150076 KB Output is correct
5 Correct 91 ms 150084 KB Output is correct
6 Correct 110 ms 150068 KB Output is correct
7 Correct 1217 ms 184284 KB Output is correct
8 Correct 2531 ms 235572 KB Output is correct
9 Correct 2611 ms 236092 KB Output is correct
10 Correct 2563 ms 236348 KB Output is correct
11 Correct 955 ms 180548 KB Output is correct
12 Correct 1815 ms 207688 KB Output is correct
13 Correct 2021 ms 211672 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 150064 KB Output is correct
2 Correct 93 ms 150084 KB Output is correct
3 Correct 94 ms 150100 KB Output is correct
4 Correct 103 ms 150088 KB Output is correct
5 Correct 92 ms 150128 KB Output is correct
6 Correct 104 ms 150172 KB Output is correct
7 Correct 108 ms 150088 KB Output is correct
8 Correct 93 ms 150108 KB Output is correct
9 Correct 94 ms 150024 KB Output is correct
10 Correct 90 ms 150116 KB Output is correct
11 Correct 103 ms 150084 KB Output is correct
12 Correct 92 ms 150084 KB Output is correct
13 Correct 98 ms 150048 KB Output is correct
14 Correct 93 ms 150124 KB Output is correct
15 Correct 92 ms 150080 KB Output is correct
16 Correct 90 ms 150144 KB Output is correct
17 Correct 108 ms 150340 KB Output is correct
18 Correct 111 ms 150340 KB Output is correct
19 Correct 110 ms 150316 KB Output is correct
20 Correct 93 ms 150140 KB Output is correct
21 Correct 108 ms 150212 KB Output is correct
22 Correct 92 ms 150208 KB Output is correct
23 Correct 109 ms 150208 KB Output is correct
24 Correct 93 ms 150212 KB Output is correct
25 Correct 104 ms 151924 KB Output is correct
26 Correct 109 ms 151876 KB Output is correct
27 Correct 107 ms 151936 KB Output is correct
28 Correct 121 ms 150672 KB Output is correct
29 Correct 117 ms 151064 KB Output is correct
30 Correct 108 ms 151076 KB Output is correct
31 Correct 126 ms 151084 KB Output is correct
32 Correct 116 ms 151108 KB Output is correct
33 Correct 229 ms 164768 KB Output is correct
34 Correct 218 ms 158128 KB Output is correct
35 Correct 224 ms 164788 KB Output is correct
36 Correct 222 ms 158068 KB Output is correct
37 Correct 306 ms 172608 KB Output is correct
38 Correct 297 ms 172528 KB Output is correct
39 Correct 316 ms 172888 KB Output is correct
40 Correct 280 ms 171568 KB Output is correct
41 Correct 248 ms 156836 KB Output is correct
42 Correct 246 ms 157736 KB Output is correct
43 Correct 318 ms 160808 KB Output is correct
44 Correct 319 ms 162872 KB Output is correct
45 Correct 213 ms 156412 KB Output is correct
46 Correct 221 ms 156580 KB Output is correct
47 Correct 367 ms 161536 KB Output is correct
48 Correct 362 ms 162468 KB Output is correct
49 Correct 100 ms 150260 KB Output is correct
50 Correct 91 ms 150216 KB Output is correct
51 Correct 90 ms 150088 KB Output is correct
52 Correct 95 ms 150112 KB Output is correct
53 Correct 110 ms 150240 KB Output is correct
54 Correct 93 ms 150152 KB Output is correct
55 Correct 91 ms 150196 KB Output is correct
56 Correct 107 ms 150220 KB Output is correct
57 Correct 93 ms 150160 KB Output is correct
58 Correct 107 ms 150124 KB Output is correct
59 Correct 112 ms 150148 KB Output is correct
60 Correct 110 ms 150068 KB Output is correct
61 Correct 1217 ms 184284 KB Output is correct
62 Correct 2531 ms 235572 KB Output is correct
63 Correct 2611 ms 236092 KB Output is correct
64 Correct 2563 ms 236348 KB Output is correct
65 Correct 955 ms 180548 KB Output is correct
66 Correct 1815 ms 207688 KB Output is correct
67 Correct 2021 ms 211672 KB Output is correct
68 Correct 91 ms 150080 KB Output is correct
69 Correct 108 ms 150048 KB Output is correct
70 Correct 92 ms 150120 KB Output is correct
71 Correct 109 ms 150076 KB Output is correct
72 Correct 91 ms 150084 KB Output is correct
73 Correct 2392 ms 343768 KB Output is correct
74 Correct 2239 ms 259792 KB Output is correct
75 Correct 2465 ms 343668 KB Output is correct
76 Correct 2155 ms 259680 KB Output is correct
77 Correct 3661 ms 442684 KB Output is correct
78 Correct 2208 ms 232492 KB Output is correct
79 Correct 2300 ms 244528 KB Output is correct
80 Correct 3786 ms 287104 KB Output is correct
81 Correct 2361 ms 247852 KB Output is correct
82 Correct 2998 ms 280104 KB Output is correct
83 Correct 3843 ms 312424 KB Output is correct
84 Correct 2846 ms 237616 KB Output is correct
85 Correct 4968 ms 308132 KB Output is correct
86 Correct 4765 ms 303320 KB Output is correct
87 Correct 2152 ms 324508 KB Output is correct
88 Correct 3752 ms 437432 KB Output is correct
89 Correct 3851 ms 441012 KB Output is correct
90 Correct 3733 ms 441652 KB Output is correct