oj.uz

Submission #1045977

# Submission time Handle Problem Language Result Execution time Memory
1045977 2024-08-06T08:48:53 Z vjudge1 Rectangles (IOI19_rect) C++17
72 / 100
 2931 ms 1048576 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
set<short>pos[2501][2501],pos2[2501][2501],stb[2501][20];
set<short> operator & (const set<short>&a,const set<short>&b){
    set<short>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-1;
}
int cnt(int l,int r,int col){
    int x=31-__builtin_clz(r-l+1);
    set<short>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:77:50: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   77 |                 stb[i][j]=stb[i][j-1]&stb[i+(1<<j-1)][j-1];
      |                                                 ~^~
rect.cpp:86:46: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   86 |             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 186 ms 590272 KB Output is correct
2 Correct 196 ms 590360 KB Output is correct
3 Correct 208 ms 590200 KB Output is correct
4 Correct 181 ms 590360 KB Output is correct
5 Correct 191 ms 590240 KB Output is correct
6 Correct 210 ms 590420 KB Output is correct
7 Correct 206 ms 590340 KB Output is correct
8 Correct 175 ms 590136 KB Output is correct
9 Correct 206 ms 590320 KB Output is correct
10 Correct 204 ms 590164 KB Output is correct
11 Correct 224 ms 590248 KB Output is correct
12 Correct 201 ms 590416 KB Output is correct
13 Correct 184 ms 590164 KB Output is correct
14 Correct 189 ms 590164 KB Output is correct
15 Correct 174 ms 590164 KB Output is correct
16 Correct 179 ms 590084 KB Output is correct
17 Correct 191 ms 590152 KB Output is correct
18 Correct 186 ms 590124 KB Output is correct
19 Correct 180 ms 590160 KB Output is correct
20 Correct 173 ms 590240 KB Output is correct
21 Correct 182 ms 590184 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 590272 KB Output is correct
2 Correct 196 ms 590360 KB Output is correct
3 Correct 208 ms 590200 KB Output is correct
4 Correct 181 ms 590360 KB Output is correct
5 Correct 191 ms 590240 KB Output is correct
6 Correct 210 ms 590420 KB Output is correct
7 Correct 206 ms 590340 KB Output is correct
8 Correct 175 ms 590136 KB Output is correct
9 Correct 206 ms 590320 KB Output is correct
10 Correct 204 ms 590164 KB Output is correct
11 Correct 224 ms 590248 KB Output is correct
12 Correct 201 ms 590416 KB Output is correct
13 Correct 184 ms 590164 KB Output is correct
14 Correct 189 ms 590164 KB Output is correct
15 Correct 174 ms 590164 KB Output is correct
16 Correct 179 ms 590084 KB Output is correct
17 Correct 191 ms 590152 KB Output is correct
18 Correct 186 ms 590124 KB Output is correct
19 Correct 180 ms 590160 KB Output is correct
20 Correct 173 ms 590240 KB Output is correct
21 Correct 182 ms 590184 KB Output is correct
22 Correct 200 ms 590972 KB Output is correct
23 Correct 184 ms 591096 KB Output is correct
24 Correct 252 ms 591168 KB Output is correct
25 Correct 220 ms 590676 KB Output is correct
26 Correct 186 ms 591288 KB Output is correct
27 Correct 189 ms 591124 KB Output is correct
28 Correct 184 ms 591076 KB Output is correct
29 Correct 188 ms 590536 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 590272 KB Output is correct
2 Correct 196 ms 590360 KB Output is correct
3 Correct 208 ms 590200 KB Output is correct
4 Correct 181 ms 590360 KB Output is correct
5 Correct 191 ms 590240 KB Output is correct
6 Correct 210 ms 590420 KB Output is correct
7 Correct 206 ms 590340 KB Output is correct
8 Correct 175 ms 590136 KB Output is correct
9 Correct 206 ms 590320 KB Output is correct
10 Correct 204 ms 590164 KB Output is correct
11 Correct 224 ms 590248 KB Output is correct
12 Correct 201 ms 590416 KB Output is correct
13 Correct 184 ms 590164 KB Output is correct
14 Correct 189 ms 590164 KB Output is correct
15 Correct 174 ms 590164 KB Output is correct
16 Correct 179 ms 590084 KB Output is correct
17 Correct 200 ms 590972 KB Output is correct
18 Correct 184 ms 591096 KB Output is correct
19 Correct 252 ms 591168 KB Output is correct
20 Correct 220 ms 590676 KB Output is correct
21 Correct 186 ms 591288 KB Output is correct
22 Correct 189 ms 591124 KB Output is correct
23 Correct 184 ms 591076 KB Output is correct
24 Correct 188 ms 590536 KB Output is correct
25 Correct 191 ms 590152 KB Output is correct
26 Correct 186 ms 590124 KB Output is correct
27 Correct 180 ms 590160 KB Output is correct
28 Correct 173 ms 590240 KB Output is correct
29 Correct 182 ms 590184 KB Output is correct
30 Correct 213 ms 595696 KB Output is correct
31 Correct 220 ms 595656 KB Output is correct
32 Correct 206 ms 595732 KB Output is correct
33 Correct 201 ms 592468 KB Output is correct
34 Correct 215 ms 595272 KB Output is correct
35 Correct 219 ms 595540 KB Output is correct
36 Correct 208 ms 595252 KB Output is correct
37 Correct 200 ms 595172 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 590272 KB Output is correct
2 Correct 196 ms 590360 KB Output is correct
3 Correct 208 ms 590200 KB Output is correct
4 Correct 181 ms 590360 KB Output is correct
5 Correct 191 ms 590240 KB Output is correct
6 Correct 210 ms 590420 KB Output is correct
7 Correct 206 ms 590340 KB Output is correct
8 Correct 175 ms 590136 KB Output is correct
9 Correct 206 ms 590320 KB Output is correct
10 Correct 204 ms 590164 KB Output is correct
11 Correct 224 ms 590248 KB Output is correct
12 Correct 201 ms 590416 KB Output is correct
13 Correct 184 ms 590164 KB Output is correct
14 Correct 189 ms 590164 KB Output is correct
15 Correct 174 ms 590164 KB Output is correct
16 Correct 179 ms 590084 KB Output is correct
17 Correct 200 ms 590972 KB Output is correct
18 Correct 184 ms 591096 KB Output is correct
19 Correct 252 ms 591168 KB Output is correct
20 Correct 220 ms 590676 KB Output is correct
21 Correct 186 ms 591288 KB Output is correct
22 Correct 189 ms 591124 KB Output is correct
23 Correct 184 ms 591076 KB Output is correct
24 Correct 188 ms 590536 KB Output is correct
25 Correct 213 ms 595696 KB Output is correct
26 Correct 220 ms 595656 KB Output is correct
27 Correct 206 ms 595732 KB Output is correct
28 Correct 201 ms 592468 KB Output is correct
29 Correct 215 ms 595272 KB Output is correct
30 Correct 219 ms 595540 KB Output is correct
31 Correct 208 ms 595252 KB Output is correct
32 Correct 200 ms 595172 KB Output is correct
33 Correct 191 ms 590152 KB Output is correct
34 Correct 186 ms 590124 KB Output is correct
35 Correct 180 ms 590160 KB Output is correct
36 Correct 173 ms 590240 KB Output is correct
37 Correct 182 ms 590184 KB Output is correct
38 Correct 357 ms 625044 KB Output is correct
39 Correct 379 ms 624936 KB Output is correct
40 Correct 358 ms 624876 KB Output is correct
41 Correct 373 ms 625080 KB Output is correct
42 Correct 578 ms 653028 KB Output is correct
43 Correct 584 ms 653012 KB Output is correct
44 Correct 572 ms 653312 KB Output is correct
45 Correct 692 ms 649392 KB Output is correct
46 Correct 339 ms 608972 KB Output is correct
47 Correct 357 ms 617100 KB Output is correct
48 Correct 496 ms 649744 KB Output is correct
49 Correct 522 ms 652216 KB Output is correct
50 Correct 354 ms 620992 KB Output is correct
51 Correct 335 ms 621024 KB Output is correct
52 Correct 522 ms 647868 KB Output is correct
53 Correct 520 ms 648728 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 591708 KB Output is correct
2 Correct 177 ms 591456 KB Output is correct
3 Correct 171 ms 590172 KB Output is correct
4 Correct 177 ms 590328 KB Output is correct
5 Correct 185 ms 590476 KB Output is correct
6 Correct 176 ms 590420 KB Output is correct
7 Correct 179 ms 590524 KB Output is correct
8 Correct 175 ms 590532 KB Output is correct
9 Correct 177 ms 590420 KB Output is correct
10 Correct 179 ms 590160 KB Output is correct
11 Correct 190 ms 590180 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 590152 KB Output is correct
2 Correct 186 ms 590124 KB Output is correct
3 Correct 180 ms 590160 KB Output is correct
4 Correct 173 ms 590240 KB Output is correct
5 Correct 182 ms 590184 KB Output is correct
6 Correct 178 ms 590160 KB Output is correct
7 Correct 1044 ms 701848 KB Output is correct
8 Correct 2145 ms 829848 KB Output is correct
9 Correct 2190 ms 830740 KB Output is correct
10 Correct 2325 ms 830808 KB Output is correct
11 Correct 546 ms 620488 KB Output is correct
12 Correct 947 ms 647824 KB Output is correct
13 Correct 994 ms 651596 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 590272 KB Output is correct
2 Correct 196 ms 590360 KB Output is correct
3 Correct 208 ms 590200 KB Output is correct
4 Correct 181 ms 590360 KB Output is correct
5 Correct 191 ms 590240 KB Output is correct
6 Correct 210 ms 590420 KB Output is correct
7 Correct 206 ms 590340 KB Output is correct
8 Correct 175 ms 590136 KB Output is correct
9 Correct 206 ms 590320 KB Output is correct
10 Correct 204 ms 590164 KB Output is correct
11 Correct 224 ms 590248 KB Output is correct
12 Correct 201 ms 590416 KB Output is correct
13 Correct 184 ms 590164 KB Output is correct
14 Correct 189 ms 590164 KB Output is correct
15 Correct 174 ms 590164 KB Output is correct
16 Correct 179 ms 590084 KB Output is correct
17 Correct 200 ms 590972 KB Output is correct
18 Correct 184 ms 591096 KB Output is correct
19 Correct 252 ms 591168 KB Output is correct
20 Correct 220 ms 590676 KB Output is correct
21 Correct 186 ms 591288 KB Output is correct
22 Correct 189 ms 591124 KB Output is correct
23 Correct 184 ms 591076 KB Output is correct
24 Correct 188 ms 590536 KB Output is correct
25 Correct 213 ms 595696 KB Output is correct
26 Correct 220 ms 595656 KB Output is correct
27 Correct 206 ms 595732 KB Output is correct
28 Correct 201 ms 592468 KB Output is correct
29 Correct 215 ms 595272 KB Output is correct
30 Correct 219 ms 595540 KB Output is correct
31 Correct 208 ms 595252 KB Output is correct
32 Correct 200 ms 595172 KB Output is correct
33 Correct 357 ms 625044 KB Output is correct
34 Correct 379 ms 624936 KB Output is correct
35 Correct 358 ms 624876 KB Output is correct
36 Correct 373 ms 625080 KB Output is correct
37 Correct 578 ms 653028 KB Output is correct
38 Correct 584 ms 653012 KB Output is correct
39 Correct 572 ms 653312 KB Output is correct
40 Correct 692 ms 649392 KB Output is correct
41 Correct 339 ms 608972 KB Output is correct
42 Correct 357 ms 617100 KB Output is correct
43 Correct 496 ms 649744 KB Output is correct
44 Correct 522 ms 652216 KB Output is correct
45 Correct 354 ms 620992 KB Output is correct
46 Correct 335 ms 621024 KB Output is correct
47 Correct 522 ms 647868 KB Output is correct
48 Correct 520 ms 648728 KB Output is correct
49 Correct 176 ms 591708 KB Output is correct
50 Correct 177 ms 591456 KB Output is correct
51 Correct 171 ms 590172 KB Output is correct
52 Correct 177 ms 590328 KB Output is correct
53 Correct 185 ms 590476 KB Output is correct
54 Correct 176 ms 590420 KB Output is correct
55 Correct 179 ms 590524 KB Output is correct
56 Correct 175 ms 590532 KB Output is correct
57 Correct 177 ms 590420 KB Output is correct
58 Correct 179 ms 590160 KB Output is correct
59 Correct 190 ms 590180 KB Output is correct
60 Correct 178 ms 590160 KB Output is correct
61 Correct 1044 ms 701848 KB Output is correct
62 Correct 2145 ms 829848 KB Output is correct
63 Correct 2190 ms 830740 KB Output is correct
64 Correct 2325 ms 830808 KB Output is correct
65 Correct 546 ms 620488 KB Output is correct
66 Correct 947 ms 647824 KB Output is correct
67 Correct 994 ms 651596 KB Output is correct
68 Correct 191 ms 590152 KB Output is correct
69 Correct 186 ms 590124 KB Output is correct
70 Correct 180 ms 590160 KB Output is correct
71 Correct 173 ms 590240 KB Output is correct
72 Correct 182 ms 590184 KB Output is correct
73 Correct 2673 ms 1044988 KB Output is correct
74 Correct 2931 ms 1044848 KB Output is correct
75 Correct 2773 ms 1044212 KB Output is correct
76 Correct 2837 ms 1039832 KB Output is correct
77 Runtime error 1028 ms 1048576 KB Execution killed with signal 9
78 Halted 0 ms 0 KB -