oj.uz

Submission #1046014

# Submission time Handle Problem Language Result Execution time Memory
1046014 2024-08-06T09:00:22 Z vjudge1 Rectangles (IOI19_rect) C++17
72 / 100
 5000 ms 866944 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#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:81:50: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   81 |                 stb[i][j]=stb[i][j-1]&stb[i+(1<<j-1)][j-1];
      |                                                 ~^~
rect.cpp:90:46: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   90 |             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 40 ms 295252 KB Output is correct
2 Correct 39 ms 295260 KB Output is correct
3 Correct 40 ms 295260 KB Output is correct
4 Correct 39 ms 295260 KB Output is correct
5 Correct 40 ms 295260 KB Output is correct
6 Correct 42 ms 295260 KB Output is correct
7 Correct 40 ms 295300 KB Output is correct
8 Correct 40 ms 295304 KB Output is correct
9 Correct 40 ms 295260 KB Output is correct
10 Correct 40 ms 295248 KB Output is correct
11 Correct 40 ms 295260 KB Output is correct
12 Correct 45 ms 295392 KB Output is correct
13 Correct 43 ms 295516 KB Output is correct
14 Correct 41 ms 295252 KB Output is correct
15 Correct 41 ms 295252 KB Output is correct
16 Correct 48 ms 295248 KB Output is correct
17 Correct 40 ms 295248 KB Output is correct
18 Correct 47 ms 295252 KB Output is correct
19 Correct 55 ms 295348 KB Output is correct
20 Correct 40 ms 295248 KB Output is correct
21 Correct 41 ms 295284 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 295252 KB Output is correct
2 Correct 39 ms 295260 KB Output is correct
3 Correct 40 ms 295260 KB Output is correct
4 Correct 39 ms 295260 KB Output is correct
5 Correct 40 ms 295260 KB Output is correct
6 Correct 42 ms 295260 KB Output is correct
7 Correct 40 ms 295300 KB Output is correct
8 Correct 40 ms 295304 KB Output is correct
9 Correct 40 ms 295260 KB Output is correct
10 Correct 40 ms 295248 KB Output is correct
11 Correct 40 ms 295260 KB Output is correct
12 Correct 45 ms 295392 KB Output is correct
13 Correct 43 ms 295516 KB Output is correct
14 Correct 41 ms 295252 KB Output is correct
15 Correct 41 ms 295252 KB Output is correct
16 Correct 48 ms 295248 KB Output is correct
17 Correct 40 ms 295248 KB Output is correct
18 Correct 47 ms 295252 KB Output is correct
19 Correct 55 ms 295348 KB Output is correct
20 Correct 40 ms 295248 KB Output is correct
21 Correct 41 ms 295284 KB Output is correct
22 Correct 45 ms 295988 KB Output is correct
23 Correct 43 ms 296020 KB Output is correct
24 Correct 47 ms 296020 KB Output is correct
25 Correct 44 ms 295824 KB Output is correct
26 Correct 44 ms 296020 KB Output is correct
27 Correct 43 ms 295920 KB Output is correct
28 Correct 46 ms 295884 KB Output is correct
29 Correct 42 ms 295476 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 295252 KB Output is correct
2 Correct 39 ms 295260 KB Output is correct
3 Correct 40 ms 295260 KB Output is correct
4 Correct 39 ms 295260 KB Output is correct
5 Correct 40 ms 295260 KB Output is correct
6 Correct 42 ms 295260 KB Output is correct
7 Correct 40 ms 295300 KB Output is correct
8 Correct 40 ms 295304 KB Output is correct
9 Correct 40 ms 295260 KB Output is correct
10 Correct 40 ms 295248 KB Output is correct
11 Correct 40 ms 295260 KB Output is correct
12 Correct 45 ms 295392 KB Output is correct
13 Correct 43 ms 295516 KB Output is correct
14 Correct 41 ms 295252 KB Output is correct
15 Correct 41 ms 295252 KB Output is correct
16 Correct 48 ms 295248 KB Output is correct
17 Correct 45 ms 295988 KB Output is correct
18 Correct 43 ms 296020 KB Output is correct
19 Correct 47 ms 296020 KB Output is correct
20 Correct 44 ms 295824 KB Output is correct
21 Correct 44 ms 296020 KB Output is correct
22 Correct 43 ms 295920 KB Output is correct
23 Correct 46 ms 295884 KB Output is correct
24 Correct 42 ms 295476 KB Output is correct
25 Correct 40 ms 295248 KB Output is correct
26 Correct 47 ms 295252 KB Output is correct
27 Correct 55 ms 295348 KB Output is correct
28 Correct 40 ms 295248 KB Output is correct
29 Correct 41 ms 295284 KB Output is correct
30 Correct 75 ms 299076 KB Output is correct
31 Correct 65 ms 299288 KB Output is correct
32 Correct 65 ms 299224 KB Output is correct
33 Correct 54 ms 298484 KB Output is correct
34 Correct 60 ms 299248 KB Output is correct
35 Correct 74 ms 299220 KB Output is correct
36 Correct 63 ms 299228 KB Output is correct
37 Correct 69 ms 299216 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 295252 KB Output is correct
2 Correct 39 ms 295260 KB Output is correct
3 Correct 40 ms 295260 KB Output is correct
4 Correct 39 ms 295260 KB Output is correct
5 Correct 40 ms 295260 KB Output is correct
6 Correct 42 ms 295260 KB Output is correct
7 Correct 40 ms 295300 KB Output is correct
8 Correct 40 ms 295304 KB Output is correct
9 Correct 40 ms 295260 KB Output is correct
10 Correct 40 ms 295248 KB Output is correct
11 Correct 40 ms 295260 KB Output is correct
12 Correct 45 ms 295392 KB Output is correct
13 Correct 43 ms 295516 KB Output is correct
14 Correct 41 ms 295252 KB Output is correct
15 Correct 41 ms 295252 KB Output is correct
16 Correct 48 ms 295248 KB Output is correct
17 Correct 45 ms 295988 KB Output is correct
18 Correct 43 ms 296020 KB Output is correct
19 Correct 47 ms 296020 KB Output is correct
20 Correct 44 ms 295824 KB Output is correct
21 Correct 44 ms 296020 KB Output is correct
22 Correct 43 ms 295920 KB Output is correct
23 Correct 46 ms 295884 KB Output is correct
24 Correct 42 ms 295476 KB Output is correct
25 Correct 75 ms 299076 KB Output is correct
26 Correct 65 ms 299288 KB Output is correct
27 Correct 65 ms 299224 KB Output is correct
28 Correct 54 ms 298484 KB Output is correct
29 Correct 60 ms 299248 KB Output is correct
30 Correct 74 ms 299220 KB Output is correct
31 Correct 63 ms 299228 KB Output is correct
32 Correct 69 ms 299216 KB Output is correct
33 Correct 40 ms 295248 KB Output is correct
34 Correct 47 ms 295252 KB Output is correct
35 Correct 55 ms 295348 KB Output is correct
36 Correct 40 ms 295248 KB Output is correct
37 Correct 41 ms 295284 KB Output is correct
38 Correct 193 ms 334500 KB Output is correct
39 Correct 185 ms 336824 KB Output is correct
40 Correct 227 ms 336820 KB Output is correct
41 Correct 185 ms 338360 KB Output is correct
42 Correct 382 ms 340248 KB Output is correct
43 Correct 380 ms 339824 KB Output is correct
44 Correct 382 ms 339516 KB Output is correct
45 Correct 360 ms 336972 KB Output is correct
46 Correct 176 ms 332224 KB Output is correct
47 Correct 198 ms 334264 KB Output is correct
48 Correct 297 ms 340676 KB Output is correct
49 Correct 314 ms 340156 KB Output is correct
50 Correct 173 ms 317736 KB Output is correct
51 Correct 196 ms 319176 KB Output is correct
52 Correct 318 ms 339516 KB Output is correct
53 Correct 303 ms 339376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 296272 KB Output is correct
2 Correct 42 ms 296280 KB Output is correct
3 Correct 43 ms 295508 KB Output is correct
4 Correct 41 ms 295284 KB Output is correct
5 Correct 41 ms 295704 KB Output is correct
6 Correct 40 ms 295768 KB Output is correct
7 Correct 47 ms 295508 KB Output is correct
8 Correct 41 ms 295512 KB Output is correct
9 Correct 43 ms 295728 KB Output is correct
10 Correct 39 ms 295248 KB Output is correct
11 Correct 41 ms 295284 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 295248 KB Output is correct
2 Correct 47 ms 295252 KB Output is correct
3 Correct 55 ms 295348 KB Output is correct
4 Correct 40 ms 295248 KB Output is correct
5 Correct 41 ms 295284 KB Output is correct
6 Correct 40 ms 295260 KB Output is correct
7 Correct 986 ms 513960 KB Output is correct
8 Correct 2114 ms 766124 KB Output is correct
9 Correct 2143 ms 768700 KB Output is correct
10 Correct 2057 ms 768272 KB Output is correct
11 Correct 501 ms 512336 KB Output is correct
12 Correct 910 ms 707924 KB Output is correct
13 Correct 1004 ms 735312 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 295252 KB Output is correct
2 Correct 39 ms 295260 KB Output is correct
3 Correct 40 ms 295260 KB Output is correct
4 Correct 39 ms 295260 KB Output is correct
5 Correct 40 ms 295260 KB Output is correct
6 Correct 42 ms 295260 KB Output is correct
7 Correct 40 ms 295300 KB Output is correct
8 Correct 40 ms 295304 KB Output is correct
9 Correct 40 ms 295260 KB Output is correct
10 Correct 40 ms 295248 KB Output is correct
11 Correct 40 ms 295260 KB Output is correct
12 Correct 45 ms 295392 KB Output is correct
13 Correct 43 ms 295516 KB Output is correct
14 Correct 41 ms 295252 KB Output is correct
15 Correct 41 ms 295252 KB Output is correct
16 Correct 48 ms 295248 KB Output is correct
17 Correct 45 ms 295988 KB Output is correct
18 Correct 43 ms 296020 KB Output is correct
19 Correct 47 ms 296020 KB Output is correct
20 Correct 44 ms 295824 KB Output is correct
21 Correct 44 ms 296020 KB Output is correct
22 Correct 43 ms 295920 KB Output is correct
23 Correct 46 ms 295884 KB Output is correct
24 Correct 42 ms 295476 KB Output is correct
25 Correct 75 ms 299076 KB Output is correct
26 Correct 65 ms 299288 KB Output is correct
27 Correct 65 ms 299224 KB Output is correct
28 Correct 54 ms 298484 KB Output is correct
29 Correct 60 ms 299248 KB Output is correct
30 Correct 74 ms 299220 KB Output is correct
31 Correct 63 ms 299228 KB Output is correct
32 Correct 69 ms 299216 KB Output is correct
33 Correct 193 ms 334500 KB Output is correct
34 Correct 185 ms 336824 KB Output is correct
35 Correct 227 ms 336820 KB Output is correct
36 Correct 185 ms 338360 KB Output is correct
37 Correct 382 ms 340248 KB Output is correct
38 Correct 380 ms 339824 KB Output is correct
39 Correct 382 ms 339516 KB Output is correct
40 Correct 360 ms 336972 KB Output is correct
41 Correct 176 ms 332224 KB Output is correct
42 Correct 198 ms 334264 KB Output is correct
43 Correct 297 ms 340676 KB Output is correct
44 Correct 314 ms 340156 KB Output is correct
45 Correct 173 ms 317736 KB Output is correct
46 Correct 196 ms 319176 KB Output is correct
47 Correct 318 ms 339516 KB Output is correct
48 Correct 303 ms 339376 KB Output is correct
49 Correct 44 ms 296272 KB Output is correct
50 Correct 42 ms 296280 KB Output is correct
51 Correct 43 ms 295508 KB Output is correct
52 Correct 41 ms 295284 KB Output is correct
53 Correct 41 ms 295704 KB Output is correct
54 Correct 40 ms 295768 KB Output is correct
55 Correct 47 ms 295508 KB Output is correct
56 Correct 41 ms 295512 KB Output is correct
57 Correct 43 ms 295728 KB Output is correct
58 Correct 39 ms 295248 KB Output is correct
59 Correct 41 ms 295284 KB Output is correct
60 Correct 40 ms 295260 KB Output is correct
61 Correct 986 ms 513960 KB Output is correct
62 Correct 2114 ms 766124 KB Output is correct
63 Correct 2143 ms 768700 KB Output is correct
64 Correct 2057 ms 768272 KB Output is correct
65 Correct 501 ms 512336 KB Output is correct
66 Correct 910 ms 707924 KB Output is correct
67 Correct 1004 ms 735312 KB Output is correct
68 Correct 40 ms 295248 KB Output is correct
69 Correct 47 ms 295252 KB Output is correct
70 Correct 55 ms 295348 KB Output is correct
71 Correct 40 ms 295248 KB Output is correct
72 Correct 41 ms 295284 KB Output is correct
73 Correct 2204 ms 802912 KB Output is correct
74 Correct 2300 ms 827792 KB Output is correct
75 Correct 2251 ms 826772 KB Output is correct
76 Correct 2192 ms 842828 KB Output is correct
77 Execution timed out 5085 ms 866944 KB Time limit exceeded
78 Halted 0 ms 0 KB -