oj.uz

Submission #1046143

# Submission time Handle Problem Language Result Execution time Memory
1046143 2024-08-06T10:31:35 Z boyliguanhan Rectangles (IOI19_rect) C++17
100 / 100
 4785 ms 928100 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)
#define all(x) x.begin(),x.end()
#define HAS(a,b) (lower_bound(all(a),b)!=upper_bound(all(a),b))
vector<int>pos[2501][2501],pos2[2501][2501],stb[2501][20];
vector<int> operator & (const vector<int>&a,const vector<int>&b){
    vector<int>c;
    if(a.size()<b.size()){
        for(auto i:a)
            if(HAS(b,i))
                c.push_back(i);
    } else for(auto i:b)
        if(HAS(a,i))
            c.push_back(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(HAS(stb[beg][i],r2))
            beg+=1<<i;
    return beg-1;
}
int cnt(int l,int r,int col){
    int x=31-__builtin_clz(r-l+1);
    vector<int>k=stb[l][x]&stb[r-(1<<x)+1][x];
    return upper_bound(k.begin(),k.end(),res[CC++])-k.begin();
}
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].push_back(stk.top()-1),stk.pop();
            if(stk.size()){
                pos[i][j+1].push_back(stk.top()-1);
                if(a[i][stk.top()]==a[i][j])
                    stk.pop();
            }
            stk.push(j);
            if(pos[i][j+1].size())
                pos[i][j+1].erase(pos[i][j+1].begin());
        }
    }
    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].push_back(stk.top()-1),stk.pop(); 
            if(stk.size()){
                pos2[i+1][j].push_back(stk.top()-1);
                if(a[stk.top()][j]==a[i][j])
                    stk.pop();
            }
            stk.push(i);
            if(pos2[i+1][j].size())
                pos2[i+1][j].erase(pos2[i+1][j].begin());
        }
    }
    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:82:50: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   82 |                 stb[i][j]=stb[i][j-1]&stb[i+(1<<j-1)][j-1];
      |                                                 ~^~
rect.cpp:91:46: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   91 |             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 39 ms 295260 KB Output is correct
2 Correct 42 ms 295256 KB Output is correct
3 Correct 40 ms 295392 KB Output is correct
4 Correct 42 ms 295260 KB Output is correct
5 Correct 40 ms 295248 KB Output is correct
6 Correct 40 ms 295260 KB Output is correct
7 Correct 46 ms 295252 KB Output is correct
8 Correct 39 ms 295260 KB Output is correct
9 Correct 42 ms 295248 KB Output is correct
10 Correct 40 ms 295300 KB Output is correct
11 Correct 40 ms 295248 KB Output is correct
12 Correct 43 ms 295252 KB Output is correct
13 Correct 41 ms 295248 KB Output is correct
14 Correct 42 ms 295252 KB Output is correct
15 Correct 41 ms 295248 KB Output is correct
16 Correct 44 ms 295200 KB Output is correct
17 Correct 44 ms 295308 KB Output is correct
18 Correct 39 ms 295252 KB Output is correct
19 Correct 41 ms 295280 KB Output is correct
20 Correct 47 ms 295180 KB Output is correct
21 Correct 40 ms 295252 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 295260 KB Output is correct
2 Correct 42 ms 295256 KB Output is correct
3 Correct 40 ms 295392 KB Output is correct
4 Correct 42 ms 295260 KB Output is correct
5 Correct 40 ms 295248 KB Output is correct
6 Correct 40 ms 295260 KB Output is correct
7 Correct 46 ms 295252 KB Output is correct
8 Correct 39 ms 295260 KB Output is correct
9 Correct 42 ms 295248 KB Output is correct
10 Correct 40 ms 295300 KB Output is correct
11 Correct 40 ms 295248 KB Output is correct
12 Correct 43 ms 295252 KB Output is correct
13 Correct 41 ms 295248 KB Output is correct
14 Correct 42 ms 295252 KB Output is correct
15 Correct 41 ms 295248 KB Output is correct
16 Correct 44 ms 295200 KB Output is correct
17 Correct 44 ms 295308 KB Output is correct
18 Correct 39 ms 295252 KB Output is correct
19 Correct 41 ms 295280 KB Output is correct
20 Correct 47 ms 295180 KB Output is correct
21 Correct 40 ms 295252 KB Output is correct
22 Correct 42 ms 295968 KB Output is correct
23 Correct 42 ms 295900 KB Output is correct
24 Correct 52 ms 296016 KB Output is correct
25 Correct 41 ms 295772 KB Output is correct
26 Correct 42 ms 296020 KB Output is correct
27 Correct 42 ms 296016 KB Output is correct
28 Correct 43 ms 295932 KB Output is correct
29 Correct 41 ms 295516 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 295260 KB Output is correct
2 Correct 42 ms 295256 KB Output is correct
3 Correct 40 ms 295392 KB Output is correct
4 Correct 42 ms 295260 KB Output is correct
5 Correct 40 ms 295248 KB Output is correct
6 Correct 40 ms 295260 KB Output is correct
7 Correct 46 ms 295252 KB Output is correct
8 Correct 39 ms 295260 KB Output is correct
9 Correct 42 ms 295248 KB Output is correct
10 Correct 40 ms 295300 KB Output is correct
11 Correct 40 ms 295248 KB Output is correct
12 Correct 43 ms 295252 KB Output is correct
13 Correct 41 ms 295248 KB Output is correct
14 Correct 42 ms 295252 KB Output is correct
15 Correct 41 ms 295248 KB Output is correct
16 Correct 44 ms 295200 KB Output is correct
17 Correct 42 ms 295968 KB Output is correct
18 Correct 42 ms 295900 KB Output is correct
19 Correct 52 ms 296016 KB Output is correct
20 Correct 41 ms 295772 KB Output is correct
21 Correct 42 ms 296020 KB Output is correct
22 Correct 42 ms 296016 KB Output is correct
23 Correct 43 ms 295932 KB Output is correct
24 Correct 41 ms 295516 KB Output is correct
25 Correct 44 ms 295308 KB Output is correct
26 Correct 39 ms 295252 KB Output is correct
27 Correct 41 ms 295280 KB Output is correct
28 Correct 47 ms 295180 KB Output is correct
29 Correct 40 ms 295252 KB Output is correct
30 Correct 60 ms 299468 KB Output is correct
31 Correct 61 ms 299468 KB Output is correct
32 Correct 61 ms 299504 KB Output is correct
33 Correct 50 ms 298576 KB Output is correct
34 Correct 56 ms 299416 KB Output is correct
35 Correct 57 ms 299468 KB Output is correct
36 Correct 56 ms 299536 KB Output is correct
37 Correct 57 ms 299464 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 295260 KB Output is correct
2 Correct 42 ms 295256 KB Output is correct
3 Correct 40 ms 295392 KB Output is correct
4 Correct 42 ms 295260 KB Output is correct
5 Correct 40 ms 295248 KB Output is correct
6 Correct 40 ms 295260 KB Output is correct
7 Correct 46 ms 295252 KB Output is correct
8 Correct 39 ms 295260 KB Output is correct
9 Correct 42 ms 295248 KB Output is correct
10 Correct 40 ms 295300 KB Output is correct
11 Correct 40 ms 295248 KB Output is correct
12 Correct 43 ms 295252 KB Output is correct
13 Correct 41 ms 295248 KB Output is correct
14 Correct 42 ms 295252 KB Output is correct
15 Correct 41 ms 295248 KB Output is correct
16 Correct 44 ms 295200 KB Output is correct
17 Correct 42 ms 295968 KB Output is correct
18 Correct 42 ms 295900 KB Output is correct
19 Correct 52 ms 296016 KB Output is correct
20 Correct 41 ms 295772 KB Output is correct
21 Correct 42 ms 296020 KB Output is correct
22 Correct 42 ms 296016 KB Output is correct
23 Correct 43 ms 295932 KB Output is correct
24 Correct 41 ms 295516 KB Output is correct
25 Correct 60 ms 299468 KB Output is correct
26 Correct 61 ms 299468 KB Output is correct
27 Correct 61 ms 299504 KB Output is correct
28 Correct 50 ms 298576 KB Output is correct
29 Correct 56 ms 299416 KB Output is correct
30 Correct 57 ms 299468 KB Output is correct
31 Correct 56 ms 299536 KB Output is correct
32 Correct 57 ms 299464 KB Output is correct
33 Correct 44 ms 295308 KB Output is correct
34 Correct 39 ms 295252 KB Output is correct
35 Correct 41 ms 295280 KB Output is correct
36 Correct 47 ms 295180 KB Output is correct
37 Correct 40 ms 295252 KB Output is correct
38 Correct 177 ms 338368 KB Output is correct
39 Correct 171 ms 339908 KB Output is correct
40 Correct 172 ms 340416 KB Output is correct
41 Correct 158 ms 341560 KB Output is correct
42 Correct 337 ms 342812 KB Output is correct
43 Correct 333 ms 342700 KB Output is correct
44 Correct 335 ms 342972 KB Output is correct
45 Correct 324 ms 340072 KB Output is correct
46 Correct 163 ms 333112 KB Output is correct
47 Correct 184 ms 335852 KB Output is correct
48 Correct 259 ms 341692 KB Output is correct
49 Correct 268 ms 343816 KB Output is correct
50 Correct 154 ms 319688 KB Output is correct
51 Correct 147 ms 319428 KB Output is correct
52 Correct 266 ms 342468 KB Output is correct
53 Correct 275 ms 344524 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 296416 KB Output is correct
2 Correct 43 ms 296228 KB Output is correct
3 Correct 48 ms 295504 KB Output is correct
4 Correct 47 ms 295252 KB Output is correct
5 Correct 43 ms 295760 KB Output is correct
6 Correct 41 ms 295760 KB Output is correct
7 Correct 42 ms 295704 KB Output is correct
8 Correct 40 ms 295556 KB Output is correct
9 Correct 40 ms 295656 KB Output is correct
10 Correct 42 ms 295260 KB Output is correct
11 Correct 41 ms 295504 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 295308 KB Output is correct
2 Correct 39 ms 295252 KB Output is correct
3 Correct 41 ms 295280 KB Output is correct
4 Correct 47 ms 295180 KB Output is correct
5 Correct 40 ms 295252 KB Output is correct
6 Correct 40 ms 295260 KB Output is correct
7 Correct 879 ms 519444 KB Output is correct
8 Correct 1922 ms 779772 KB Output is correct
9 Correct 1921 ms 781236 KB Output is correct
10 Correct 2001 ms 781752 KB Output is correct
11 Correct 455 ms 518432 KB Output is correct
12 Correct 918 ms 719400 KB Output is correct
13 Correct 924 ms 747684 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 295260 KB Output is correct
2 Correct 42 ms 295256 KB Output is correct
3 Correct 40 ms 295392 KB Output is correct
4 Correct 42 ms 295260 KB Output is correct
5 Correct 40 ms 295248 KB Output is correct
6 Correct 40 ms 295260 KB Output is correct
7 Correct 46 ms 295252 KB Output is correct
8 Correct 39 ms 295260 KB Output is correct
9 Correct 42 ms 295248 KB Output is correct
10 Correct 40 ms 295300 KB Output is correct
11 Correct 40 ms 295248 KB Output is correct
12 Correct 43 ms 295252 KB Output is correct
13 Correct 41 ms 295248 KB Output is correct
14 Correct 42 ms 295252 KB Output is correct
15 Correct 41 ms 295248 KB Output is correct
16 Correct 44 ms 295200 KB Output is correct
17 Correct 42 ms 295968 KB Output is correct
18 Correct 42 ms 295900 KB Output is correct
19 Correct 52 ms 296016 KB Output is correct
20 Correct 41 ms 295772 KB Output is correct
21 Correct 42 ms 296020 KB Output is correct
22 Correct 42 ms 296016 KB Output is correct
23 Correct 43 ms 295932 KB Output is correct
24 Correct 41 ms 295516 KB Output is correct
25 Correct 60 ms 299468 KB Output is correct
26 Correct 61 ms 299468 KB Output is correct
27 Correct 61 ms 299504 KB Output is correct
28 Correct 50 ms 298576 KB Output is correct
29 Correct 56 ms 299416 KB Output is correct
30 Correct 57 ms 299468 KB Output is correct
31 Correct 56 ms 299536 KB Output is correct
32 Correct 57 ms 299464 KB Output is correct
33 Correct 177 ms 338368 KB Output is correct
34 Correct 171 ms 339908 KB Output is correct
35 Correct 172 ms 340416 KB Output is correct
36 Correct 158 ms 341560 KB Output is correct
37 Correct 337 ms 342812 KB Output is correct
38 Correct 333 ms 342700 KB Output is correct
39 Correct 335 ms 342972 KB Output is correct
40 Correct 324 ms 340072 KB Output is correct
41 Correct 163 ms 333112 KB Output is correct
42 Correct 184 ms 335852 KB Output is correct
43 Correct 259 ms 341692 KB Output is correct
44 Correct 268 ms 343816 KB Output is correct
45 Correct 154 ms 319688 KB Output is correct
46 Correct 147 ms 319428 KB Output is correct
47 Correct 266 ms 342468 KB Output is correct
48 Correct 275 ms 344524 KB Output is correct
49 Correct 46 ms 296416 KB Output is correct
50 Correct 43 ms 296228 KB Output is correct
51 Correct 48 ms 295504 KB Output is correct
52 Correct 47 ms 295252 KB Output is correct
53 Correct 43 ms 295760 KB Output is correct
54 Correct 41 ms 295760 KB Output is correct
55 Correct 42 ms 295704 KB Output is correct
56 Correct 40 ms 295556 KB Output is correct
57 Correct 40 ms 295656 KB Output is correct
58 Correct 42 ms 295260 KB Output is correct
59 Correct 41 ms 295504 KB Output is correct
60 Correct 40 ms 295260 KB Output is correct
61 Correct 879 ms 519444 KB Output is correct
62 Correct 1922 ms 779772 KB Output is correct
63 Correct 1921 ms 781236 KB Output is correct
64 Correct 2001 ms 781752 KB Output is correct
65 Correct 455 ms 518432 KB Output is correct
66 Correct 918 ms 719400 KB Output is correct
67 Correct 924 ms 747684 KB Output is correct
68 Correct 44 ms 295308 KB Output is correct
69 Correct 39 ms 295252 KB Output is correct
70 Correct 41 ms 295280 KB Output is correct
71 Correct 47 ms 295180 KB Output is correct
72 Correct 40 ms 295252 KB Output is correct
73 Correct 1919 ms 849024 KB Output is correct
74 Correct 2005 ms 873184 KB Output is correct
75 Correct 2054 ms 873192 KB Output is correct
76 Correct 1911 ms 889828 KB Output is correct
77 Correct 4711 ms 915440 KB Output is correct
78 Correct 1965 ms 652936 KB Output is correct
79 Correct 2102 ms 681552 KB Output is correct
80 Correct 3390 ms 902236 KB Output is correct
81 Correct 2063 ms 670308 KB Output is correct
82 Correct 2726 ms 829384 KB Output is correct
83 Correct 3400 ms 928100 KB Output is correct
84 Correct 1994 ms 657296 KB Output is correct
85 Correct 3588 ms 928024 KB Output is correct
86 Correct 3530 ms 913944 KB Output is correct
87 Correct 2816 ms 663228 KB Output is correct
88 Correct 4785 ms 916076 KB Output is correct
89 Correct 4548 ms 915880 KB Output is correct
90 Correct 4674 ms 916208 KB Output is correct