oj.uz

Submission #1045965

# Submission time Handle Problem Language Result Execution time Memory
1045965 2024-08-06T08:46:18 Z vjudge1 Rectangles (IOI19_rect) C++17
72 / 100
 3039 ms 1048576 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
set<int>pos[2501][2501],pos2[2501][2501],stb[2501][20];
set<int> operator & (const set<int>&a,const set<int>&b){
    set<int>c;
    if(a.size()<b.size()){
        for(auto i:a)
            if(b.count(i))
                c.insert(i);
    } else for(auto i:b)
        if(a.count(i))
            c.insert(i);
    return c;
}
vector<array<int,4>> ops;
int CC;
vector<int>res;
int calc(int r1,int r2,int beg){
    /*for(int i=20;i--;)
        if(stb[beg][i].count(r2))
            beg+=1<<i;
    return beg;*/
    while(stb[++beg][0].count(r2));
    return beg-1;
}
int cnt(int l,int r,int col){
    int x=31-__builtin_clz(r-l+1);
    set<int>k=stb[l][x]&stb[r-(1<<x)+1][x];
    return distance(k.begin(),k.upper_bound(res[CC++]));
}
long long count_rectangles(std::vector<std::vector<int> > a) {
    int n=a.size(),m=a[0].size();
    int ans=0;
    for(int i=1;i<n-1;i++){
        stack<int>stk;
        stk.push(m-1);
        for(int j=m-1;j--;){
            while(stk.size()&&a[i][j]>a[i][stk.top()])
                pos[i][j+1].insert(stk.top()-1),stk.pop();
            if(stk.size()){
                pos[i][j+1].insert(stk.top()-1);
                if(a[i][stk.top()]==a[i][j])
                    stk.pop();
            }
            stk.push(j);
            pos[i][j+1].erase(j);
        }
    }
    for(int j=1;j<m-1;j++){
        stack<int>stk;
        stk.push(n-1);
        for(int i=n-1;i--;){
            while(stk.size()&&a[i][j]>a[stk.top()][j])
                pos2[i+1][j].insert(stk.top()-1),stk.pop(); 
            if(stk.size()){
                pos2[i+1][j].insert(stk.top()-1);
                if(a[stk.top()][j]==a[i][j])
                    stk.pop();
            }
            stk.push(i);
            pos2[i+1][j].erase(i);
        }
    }
    for(int j=1;j<m-1;j++)
        for(int i=1;i<n-1;i++)
            for(auto x:pos2[i][j])
                ops.push_back({i,x,j,CC++});
    res.resize(CC);
    CC=0;
    sort(ops.begin(),ops.end());
    int currr=0;
    for(auto[r1,r2,col,id]:ops){
        if(r1-currr) {
            currr=r1;
            for(int i=1;i<m-1;i++)
                stb[i][0]=pos2[r1][i];
            for(int j=1;j<20;j++) for(int i=1;i+(1<<j)<m;i++)
                stb[i][j]=stb[i][j-1]&stb[i+(1<<j-1)][j-1];
        }
        res[id]=calc(r1,r2,col);
    }
    ops.clear();
    for(int col=1;col<m-1;col++){
        for(int i=1;i<n-1;i++)
            stb[i][0]=pos[i][col];
        for(int j=1;j<20;j++) for(int i=1;i+(1<<j)<n;i++)
            stb[i][j]=stb[i][j-1]&stb[i+(1<<j-1)][j-1];
        for(int row1=1;row1<n-1;row1++)
            for(auto row2:pos2[row1][col])
                ans+=cnt(row1,row2,col);
    }
    return ans;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:79:50: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   79 |                 stb[i][j]=stb[i][j-1]&stb[i+(1<<j-1)][j-1];
      |                                                 ~^~
rect.cpp:88:46: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   88 |             stb[i][j]=stb[i][j-1]&stb[i+(1<<j-1)][j-1];
      |                                             ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 590100 KB Output is correct
2 Correct 188 ms 590428 KB Output is correct
3 Correct 162 ms 590416 KB Output is correct
4 Correct 166 ms 590256 KB Output is correct
5 Correct 198 ms 590220 KB Output is correct
6 Correct 164 ms 590536 KB Output is correct
7 Correct 169 ms 590212 KB Output is correct
8 Correct 184 ms 590160 KB Output is correct
9 Correct 197 ms 590280 KB Output is correct
10 Correct 159 ms 590296 KB Output is correct
11 Correct 158 ms 590368 KB Output is correct
12 Correct 161 ms 590160 KB Output is correct
13 Correct 160 ms 590160 KB Output is correct
14 Correct 187 ms 590160 KB Output is correct
15 Correct 183 ms 590164 KB Output is correct
16 Correct 183 ms 590288 KB Output is correct
17 Correct 162 ms 590192 KB Output is correct
18 Correct 165 ms 590160 KB Output is correct
19 Correct 163 ms 590144 KB Output is correct
20 Correct 168 ms 590204 KB Output is correct
21 Correct 191 ms 590160 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 590100 KB Output is correct
2 Correct 188 ms 590428 KB Output is correct
3 Correct 162 ms 590416 KB Output is correct
4 Correct 166 ms 590256 KB Output is correct
5 Correct 198 ms 590220 KB Output is correct
6 Correct 164 ms 590536 KB Output is correct
7 Correct 169 ms 590212 KB Output is correct
8 Correct 184 ms 590160 KB Output is correct
9 Correct 197 ms 590280 KB Output is correct
10 Correct 159 ms 590296 KB Output is correct
11 Correct 158 ms 590368 KB Output is correct
12 Correct 161 ms 590160 KB Output is correct
13 Correct 160 ms 590160 KB Output is correct
14 Correct 187 ms 590160 KB Output is correct
15 Correct 183 ms 590164 KB Output is correct
16 Correct 183 ms 590288 KB Output is correct
17 Correct 162 ms 590192 KB Output is correct
18 Correct 165 ms 590160 KB Output is correct
19 Correct 163 ms 590144 KB Output is correct
20 Correct 168 ms 590204 KB Output is correct
21 Correct 191 ms 590160 KB Output is correct
22 Correct 184 ms 591148 KB Output is correct
23 Correct 166 ms 590988 KB Output is correct
24 Correct 171 ms 591188 KB Output is correct
25 Correct 167 ms 590672 KB Output is correct
26 Correct 164 ms 591080 KB Output is correct
27 Correct 184 ms 591060 KB Output is correct
28 Correct 190 ms 591028 KB Output is correct
29 Correct 177 ms 590676 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 590100 KB Output is correct
2 Correct 188 ms 590428 KB Output is correct
3 Correct 162 ms 590416 KB Output is correct
4 Correct 166 ms 590256 KB Output is correct
5 Correct 198 ms 590220 KB Output is correct
6 Correct 164 ms 590536 KB Output is correct
7 Correct 169 ms 590212 KB Output is correct
8 Correct 184 ms 590160 KB Output is correct
9 Correct 197 ms 590280 KB Output is correct
10 Correct 159 ms 590296 KB Output is correct
11 Correct 158 ms 590368 KB Output is correct
12 Correct 161 ms 590160 KB Output is correct
13 Correct 160 ms 590160 KB Output is correct
14 Correct 187 ms 590160 KB Output is correct
15 Correct 183 ms 590164 KB Output is correct
16 Correct 183 ms 590288 KB Output is correct
17 Correct 184 ms 591148 KB Output is correct
18 Correct 166 ms 590988 KB Output is correct
19 Correct 171 ms 591188 KB Output is correct
20 Correct 167 ms 590672 KB Output is correct
21 Correct 164 ms 591080 KB Output is correct
22 Correct 184 ms 591060 KB Output is correct
23 Correct 190 ms 591028 KB Output is correct
24 Correct 177 ms 590676 KB Output is correct
25 Correct 162 ms 590192 KB Output is correct
26 Correct 165 ms 590160 KB Output is correct
27 Correct 163 ms 590144 KB Output is correct
28 Correct 168 ms 590204 KB Output is correct
29 Correct 191 ms 590160 KB Output is correct
30 Correct 214 ms 595660 KB Output is correct
31 Correct 186 ms 595672 KB Output is correct
32 Correct 195 ms 595756 KB Output is correct
33 Correct 198 ms 592416 KB Output is correct
34 Correct 205 ms 595396 KB Output is correct
35 Correct 183 ms 595404 KB Output is correct
36 Correct 197 ms 595240 KB Output is correct
37 Correct 183 ms 595152 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 590100 KB Output is correct
2 Correct 188 ms 590428 KB Output is correct
3 Correct 162 ms 590416 KB Output is correct
4 Correct 166 ms 590256 KB Output is correct
5 Correct 198 ms 590220 KB Output is correct
6 Correct 164 ms 590536 KB Output is correct
7 Correct 169 ms 590212 KB Output is correct
8 Correct 184 ms 590160 KB Output is correct
9 Correct 197 ms 590280 KB Output is correct
10 Correct 159 ms 590296 KB Output is correct
11 Correct 158 ms 590368 KB Output is correct
12 Correct 161 ms 590160 KB Output is correct
13 Correct 160 ms 590160 KB Output is correct
14 Correct 187 ms 590160 KB Output is correct
15 Correct 183 ms 590164 KB Output is correct
16 Correct 183 ms 590288 KB Output is correct
17 Correct 184 ms 591148 KB Output is correct
18 Correct 166 ms 590988 KB Output is correct
19 Correct 171 ms 591188 KB Output is correct
20 Correct 167 ms 590672 KB Output is correct
21 Correct 164 ms 591080 KB Output is correct
22 Correct 184 ms 591060 KB Output is correct
23 Correct 190 ms 591028 KB Output is correct
24 Correct 177 ms 590676 KB Output is correct
25 Correct 214 ms 595660 KB Output is correct
26 Correct 186 ms 595672 KB Output is correct
27 Correct 195 ms 595756 KB Output is correct
28 Correct 198 ms 592416 KB Output is correct
29 Correct 205 ms 595396 KB Output is correct
30 Correct 183 ms 595404 KB Output is correct
31 Correct 197 ms 595240 KB Output is correct
32 Correct 183 ms 595152 KB Output is correct
33 Correct 162 ms 590192 KB Output is correct
34 Correct 165 ms 590160 KB Output is correct
35 Correct 163 ms 590144 KB Output is correct
36 Correct 168 ms 590204 KB Output is correct
37 Correct 191 ms 590160 KB Output is correct
38 Correct 317 ms 622944 KB Output is correct
39 Correct 341 ms 622964 KB Output is correct
40 Correct 345 ms 622956 KB Output is correct
41 Correct 331 ms 622948 KB Output is correct
42 Correct 765 ms 650820 KB Output is correct
43 Correct 761 ms 650736 KB Output is correct
44 Correct 777 ms 651080 KB Output is correct
45 Correct 774 ms 647180 KB Output is correct
46 Correct 348 ms 608540 KB Output is correct
47 Correct 360 ms 616900 KB Output is correct
48 Correct 472 ms 648736 KB Output is correct
49 Correct 465 ms 649948 KB Output is correct
50 Correct 350 ms 619900 KB Output is correct
51 Correct 333 ms 620008 KB Output is correct
52 Correct 463 ms 646056 KB Output is correct
53 Correct 475 ms 646164 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 591928 KB Output is correct
2 Correct 172 ms 591492 KB Output is correct
3 Correct 163 ms 590160 KB Output is correct
4 Correct 202 ms 590176 KB Output is correct
5 Correct 166 ms 590416 KB Output is correct
6 Correct 158 ms 590416 KB Output is correct
7 Correct 161 ms 590416 KB Output is correct
8 Correct 191 ms 590480 KB Output is correct
9 Correct 182 ms 590420 KB Output is correct
10 Correct 181 ms 590136 KB Output is correct
11 Correct 163 ms 590184 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 590192 KB Output is correct
2 Correct 165 ms 590160 KB Output is correct
3 Correct 163 ms 590144 KB Output is correct
4 Correct 168 ms 590204 KB Output is correct
5 Correct 191 ms 590160 KB Output is correct
6 Correct 178 ms 590120 KB Output is correct
7 Correct 1018 ms 696284 KB Output is correct
8 Correct 2109 ms 821416 KB Output is correct
9 Correct 2201 ms 822284 KB Output is correct
10 Correct 2170 ms 822444 KB Output is correct
11 Correct 603 ms 620336 KB Output is correct
12 Correct 1031 ms 647228 KB Output is correct
13 Correct 1029 ms 651124 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 590100 KB Output is correct
2 Correct 188 ms 590428 KB Output is correct
3 Correct 162 ms 590416 KB Output is correct
4 Correct 166 ms 590256 KB Output is correct
5 Correct 198 ms 590220 KB Output is correct
6 Correct 164 ms 590536 KB Output is correct
7 Correct 169 ms 590212 KB Output is correct
8 Correct 184 ms 590160 KB Output is correct
9 Correct 197 ms 590280 KB Output is correct
10 Correct 159 ms 590296 KB Output is correct
11 Correct 158 ms 590368 KB Output is correct
12 Correct 161 ms 590160 KB Output is correct
13 Correct 160 ms 590160 KB Output is correct
14 Correct 187 ms 590160 KB Output is correct
15 Correct 183 ms 590164 KB Output is correct
16 Correct 183 ms 590288 KB Output is correct
17 Correct 184 ms 591148 KB Output is correct
18 Correct 166 ms 590988 KB Output is correct
19 Correct 171 ms 591188 KB Output is correct
20 Correct 167 ms 590672 KB Output is correct
21 Correct 164 ms 591080 KB Output is correct
22 Correct 184 ms 591060 KB Output is correct
23 Correct 190 ms 591028 KB Output is correct
24 Correct 177 ms 590676 KB Output is correct
25 Correct 214 ms 595660 KB Output is correct
26 Correct 186 ms 595672 KB Output is correct
27 Correct 195 ms 595756 KB Output is correct
28 Correct 198 ms 592416 KB Output is correct
29 Correct 205 ms 595396 KB Output is correct
30 Correct 183 ms 595404 KB Output is correct
31 Correct 197 ms 595240 KB Output is correct
32 Correct 183 ms 595152 KB Output is correct
33 Correct 317 ms 622944 KB Output is correct
34 Correct 341 ms 622964 KB Output is correct
35 Correct 345 ms 622956 KB Output is correct
36 Correct 331 ms 622948 KB Output is correct
37 Correct 765 ms 650820 KB Output is correct
38 Correct 761 ms 650736 KB Output is correct
39 Correct 777 ms 651080 KB Output is correct
40 Correct 774 ms 647180 KB Output is correct
41 Correct 348 ms 608540 KB Output is correct
42 Correct 360 ms 616900 KB Output is correct
43 Correct 472 ms 648736 KB Output is correct
44 Correct 465 ms 649948 KB Output is correct
45 Correct 350 ms 619900 KB Output is correct
46 Correct 333 ms 620008 KB Output is correct
47 Correct 463 ms 646056 KB Output is correct
48 Correct 475 ms 646164 KB Output is correct
49 Correct 184 ms 591928 KB Output is correct
50 Correct 172 ms 591492 KB Output is correct
51 Correct 163 ms 590160 KB Output is correct
52 Correct 202 ms 590176 KB Output is correct
53 Correct 166 ms 590416 KB Output is correct
54 Correct 158 ms 590416 KB Output is correct
55 Correct 161 ms 590416 KB Output is correct
56 Correct 191 ms 590480 KB Output is correct
57 Correct 182 ms 590420 KB Output is correct
58 Correct 181 ms 590136 KB Output is correct
59 Correct 163 ms 590184 KB Output is correct
60 Correct 178 ms 590120 KB Output is correct
61 Correct 1018 ms 696284 KB Output is correct
62 Correct 2109 ms 821416 KB Output is correct
63 Correct 2201 ms 822284 KB Output is correct
64 Correct 2170 ms 822444 KB Output is correct
65 Correct 603 ms 620336 KB Output is correct
66 Correct 1031 ms 647228 KB Output is correct
67 Correct 1029 ms 651124 KB Output is correct
68 Correct 162 ms 590192 KB Output is correct
69 Correct 165 ms 590160 KB Output is correct
70 Correct 163 ms 590144 KB Output is correct
71 Correct 168 ms 590204 KB Output is correct
72 Correct 191 ms 590160 KB Output is correct
73 Correct 2573 ms 1039380 KB Output is correct
74 Correct 3039 ms 1044264 KB Output is correct
75 Correct 2702 ms 1044484 KB Output is correct
76 Correct 2792 ms 1044480 KB Output is correct
77 Runtime error 916 ms 1048576 KB Execution killed with signal 9
78 Halted 0 ms 0 KB -