oj.uz

Submission #1046021

# Submission time Handle Problem Language Result Execution time Memory
1046021 2024-08-06T09:01:55 Z vjudge1 Rectangles (IOI19_rect) C++17
100 / 100
 4730 ms 930124 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 52 ms 295252 KB Output is correct
2 Correct 42 ms 295252 KB Output is correct
3 Correct 48 ms 295256 KB Output is correct
4 Correct 43 ms 295260 KB Output is correct
5 Correct 42 ms 295260 KB Output is correct
6 Correct 48 ms 295252 KB Output is correct
7 Correct 42 ms 295372 KB Output is correct
8 Correct 55 ms 295252 KB Output is correct
9 Correct 43 ms 295252 KB Output is correct
10 Correct 53 ms 295308 KB Output is correct
11 Correct 47 ms 295248 KB Output is correct
12 Correct 42 ms 295260 KB Output is correct
13 Correct 49 ms 295204 KB Output is correct
14 Correct 40 ms 295248 KB Output is correct
15 Correct 44 ms 295248 KB Output is correct
16 Correct 42 ms 295268 KB Output is correct
17 Correct 43 ms 295332 KB Output is correct
18 Correct 45 ms 295256 KB Output is correct
19 Correct 42 ms 295256 KB Output is correct
20 Correct 56 ms 295180 KB Output is correct
21 Correct 64 ms 295252 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 295252 KB Output is correct
2 Correct 42 ms 295252 KB Output is correct
3 Correct 48 ms 295256 KB Output is correct
4 Correct 43 ms 295260 KB Output is correct
5 Correct 42 ms 295260 KB Output is correct
6 Correct 48 ms 295252 KB Output is correct
7 Correct 42 ms 295372 KB Output is correct
8 Correct 55 ms 295252 KB Output is correct
9 Correct 43 ms 295252 KB Output is correct
10 Correct 53 ms 295308 KB Output is correct
11 Correct 47 ms 295248 KB Output is correct
12 Correct 42 ms 295260 KB Output is correct
13 Correct 49 ms 295204 KB Output is correct
14 Correct 40 ms 295248 KB Output is correct
15 Correct 44 ms 295248 KB Output is correct
16 Correct 42 ms 295268 KB Output is correct
17 Correct 43 ms 295332 KB Output is correct
18 Correct 45 ms 295256 KB Output is correct
19 Correct 42 ms 295256 KB Output is correct
20 Correct 56 ms 295180 KB Output is correct
21 Correct 64 ms 295252 KB Output is correct
22 Correct 46 ms 296020 KB Output is correct
23 Correct 45 ms 296020 KB Output is correct
24 Correct 58 ms 295948 KB Output is correct
25 Correct 46 ms 295856 KB Output is correct
26 Correct 45 ms 296024 KB Output is correct
27 Correct 57 ms 296016 KB Output is correct
28 Correct 47 ms 296032 KB Output is correct
29 Correct 42 ms 295540 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 295252 KB Output is correct
2 Correct 42 ms 295252 KB Output is correct
3 Correct 48 ms 295256 KB Output is correct
4 Correct 43 ms 295260 KB Output is correct
5 Correct 42 ms 295260 KB Output is correct
6 Correct 48 ms 295252 KB Output is correct
7 Correct 42 ms 295372 KB Output is correct
8 Correct 55 ms 295252 KB Output is correct
9 Correct 43 ms 295252 KB Output is correct
10 Correct 53 ms 295308 KB Output is correct
11 Correct 47 ms 295248 KB Output is correct
12 Correct 42 ms 295260 KB Output is correct
13 Correct 49 ms 295204 KB Output is correct
14 Correct 40 ms 295248 KB Output is correct
15 Correct 44 ms 295248 KB Output is correct
16 Correct 42 ms 295268 KB Output is correct
17 Correct 46 ms 296020 KB Output is correct
18 Correct 45 ms 296020 KB Output is correct
19 Correct 58 ms 295948 KB Output is correct
20 Correct 46 ms 295856 KB Output is correct
21 Correct 45 ms 296024 KB Output is correct
22 Correct 57 ms 296016 KB Output is correct
23 Correct 47 ms 296032 KB Output is correct
24 Correct 42 ms 295540 KB Output is correct
25 Correct 43 ms 295332 KB Output is correct
26 Correct 45 ms 295256 KB Output is correct
27 Correct 42 ms 295256 KB Output is correct
28 Correct 56 ms 295180 KB Output is correct
29 Correct 64 ms 295252 KB Output is correct
30 Correct 68 ms 299220 KB Output is correct
31 Correct 81 ms 299212 KB Output is correct
32 Correct 91 ms 299220 KB Output is correct
33 Correct 51 ms 298456 KB Output is correct
34 Correct 57 ms 299228 KB Output is correct
35 Correct 81 ms 299212 KB Output is correct
36 Correct 58 ms 299220 KB Output is correct
37 Correct 81 ms 299212 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 295252 KB Output is correct
2 Correct 42 ms 295252 KB Output is correct
3 Correct 48 ms 295256 KB Output is correct
4 Correct 43 ms 295260 KB Output is correct
5 Correct 42 ms 295260 KB Output is correct
6 Correct 48 ms 295252 KB Output is correct
7 Correct 42 ms 295372 KB Output is correct
8 Correct 55 ms 295252 KB Output is correct
9 Correct 43 ms 295252 KB Output is correct
10 Correct 53 ms 295308 KB Output is correct
11 Correct 47 ms 295248 KB Output is correct
12 Correct 42 ms 295260 KB Output is correct
13 Correct 49 ms 295204 KB Output is correct
14 Correct 40 ms 295248 KB Output is correct
15 Correct 44 ms 295248 KB Output is correct
16 Correct 42 ms 295268 KB Output is correct
17 Correct 46 ms 296020 KB Output is correct
18 Correct 45 ms 296020 KB Output is correct
19 Correct 58 ms 295948 KB Output is correct
20 Correct 46 ms 295856 KB Output is correct
21 Correct 45 ms 296024 KB Output is correct
22 Correct 57 ms 296016 KB Output is correct
23 Correct 47 ms 296032 KB Output is correct
24 Correct 42 ms 295540 KB Output is correct
25 Correct 68 ms 299220 KB Output is correct
26 Correct 81 ms 299212 KB Output is correct
27 Correct 91 ms 299220 KB Output is correct
28 Correct 51 ms 298456 KB Output is correct
29 Correct 57 ms 299228 KB Output is correct
30 Correct 81 ms 299212 KB Output is correct
31 Correct 58 ms 299220 KB Output is correct
32 Correct 81 ms 299212 KB Output is correct
33 Correct 43 ms 295332 KB Output is correct
34 Correct 45 ms 295256 KB Output is correct
35 Correct 42 ms 295256 KB Output is correct
36 Correct 56 ms 295180 KB Output is correct
37 Correct 64 ms 295252 KB Output is correct
38 Correct 186 ms 334784 KB Output is correct
39 Correct 196 ms 336964 KB Output is correct
40 Correct 206 ms 337088 KB Output is correct
41 Correct 161 ms 338224 KB Output is correct
42 Correct 336 ms 339464 KB Output is correct
43 Correct 345 ms 339380 KB Output is correct
44 Correct 353 ms 340164 KB Output is correct
45 Correct 318 ms 337008 KB Output is correct
46 Correct 161 ms 332224 KB Output is correct
47 Correct 181 ms 335300 KB Output is correct
48 Correct 262 ms 339904 KB Output is correct
49 Correct 307 ms 340164 KB Output is correct
50 Correct 150 ms 317640 KB Output is correct
51 Correct 183 ms 319076 KB Output is correct
52 Correct 281 ms 339372 KB Output is correct
53 Correct 309 ms 339416 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 296276 KB Output is correct
2 Correct 43 ms 296300 KB Output is correct
3 Correct 43 ms 295504 KB Output is correct
4 Correct 40 ms 295260 KB Output is correct
5 Correct 43 ms 295660 KB Output is correct
6 Correct 40 ms 295508 KB Output is correct
7 Correct 41 ms 295508 KB Output is correct
8 Correct 49 ms 295516 KB Output is correct
9 Correct 41 ms 295576 KB Output is correct
10 Correct 41 ms 295264 KB Output is correct
11 Correct 40 ms 295268 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 295332 KB Output is correct
2 Correct 45 ms 295256 KB Output is correct
3 Correct 42 ms 295256 KB Output is correct
4 Correct 56 ms 295180 KB Output is correct
5 Correct 64 ms 295252 KB Output is correct
6 Correct 39 ms 295256 KB Output is correct
7 Correct 875 ms 514008 KB Output is correct
8 Correct 1957 ms 767636 KB Output is correct
9 Correct 2024 ms 768328 KB Output is correct
10 Correct 1949 ms 768752 KB Output is correct
11 Correct 488 ms 512372 KB Output is correct
12 Correct 927 ms 708032 KB Output is correct
13 Correct 940 ms 735200 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 295252 KB Output is correct
2 Correct 42 ms 295252 KB Output is correct
3 Correct 48 ms 295256 KB Output is correct
4 Correct 43 ms 295260 KB Output is correct
5 Correct 42 ms 295260 KB Output is correct
6 Correct 48 ms 295252 KB Output is correct
7 Correct 42 ms 295372 KB Output is correct
8 Correct 55 ms 295252 KB Output is correct
9 Correct 43 ms 295252 KB Output is correct
10 Correct 53 ms 295308 KB Output is correct
11 Correct 47 ms 295248 KB Output is correct
12 Correct 42 ms 295260 KB Output is correct
13 Correct 49 ms 295204 KB Output is correct
14 Correct 40 ms 295248 KB Output is correct
15 Correct 44 ms 295248 KB Output is correct
16 Correct 42 ms 295268 KB Output is correct
17 Correct 46 ms 296020 KB Output is correct
18 Correct 45 ms 296020 KB Output is correct
19 Correct 58 ms 295948 KB Output is correct
20 Correct 46 ms 295856 KB Output is correct
21 Correct 45 ms 296024 KB Output is correct
22 Correct 57 ms 296016 KB Output is correct
23 Correct 47 ms 296032 KB Output is correct
24 Correct 42 ms 295540 KB Output is correct
25 Correct 68 ms 299220 KB Output is correct
26 Correct 81 ms 299212 KB Output is correct
27 Correct 91 ms 299220 KB Output is correct
28 Correct 51 ms 298456 KB Output is correct
29 Correct 57 ms 299228 KB Output is correct
30 Correct 81 ms 299212 KB Output is correct
31 Correct 58 ms 299220 KB Output is correct
32 Correct 81 ms 299212 KB Output is correct
33 Correct 186 ms 334784 KB Output is correct
34 Correct 196 ms 336964 KB Output is correct
35 Correct 206 ms 337088 KB Output is correct
36 Correct 161 ms 338224 KB Output is correct
37 Correct 336 ms 339464 KB Output is correct
38 Correct 345 ms 339380 KB Output is correct
39 Correct 353 ms 340164 KB Output is correct
40 Correct 318 ms 337008 KB Output is correct
41 Correct 161 ms 332224 KB Output is correct
42 Correct 181 ms 335300 KB Output is correct
43 Correct 262 ms 339904 KB Output is correct
44 Correct 307 ms 340164 KB Output is correct
45 Correct 150 ms 317640 KB Output is correct
46 Correct 183 ms 319076 KB Output is correct
47 Correct 281 ms 339372 KB Output is correct
48 Correct 309 ms 339416 KB Output is correct
49 Correct 46 ms 296276 KB Output is correct
50 Correct 43 ms 296300 KB Output is correct
51 Correct 43 ms 295504 KB Output is correct
52 Correct 40 ms 295260 KB Output is correct
53 Correct 43 ms 295660 KB Output is correct
54 Correct 40 ms 295508 KB Output is correct
55 Correct 41 ms 295508 KB Output is correct
56 Correct 49 ms 295516 KB Output is correct
57 Correct 41 ms 295576 KB Output is correct
58 Correct 41 ms 295264 KB Output is correct
59 Correct 40 ms 295268 KB Output is correct
60 Correct 39 ms 295256 KB Output is correct
61 Correct 875 ms 514008 KB Output is correct
62 Correct 1957 ms 767636 KB Output is correct
63 Correct 2024 ms 768328 KB Output is correct
64 Correct 1949 ms 768752 KB Output is correct
65 Correct 488 ms 512372 KB Output is correct
66 Correct 927 ms 708032 KB Output is correct
67 Correct 940 ms 735200 KB Output is correct
68 Correct 43 ms 295332 KB Output is correct
69 Correct 45 ms 295256 KB Output is correct
70 Correct 42 ms 295256 KB Output is correct
71 Correct 56 ms 295180 KB Output is correct
72 Correct 64 ms 295252 KB Output is correct
73 Correct 1881 ms 801752 KB Output is correct
74 Correct 1993 ms 826284 KB Output is correct
75 Correct 2054 ms 826768 KB Output is correct
76 Correct 1972 ms 842968 KB Output is correct
77 Correct 4584 ms 867324 KB Output is correct
78 Correct 1997 ms 653720 KB Output is correct
79 Correct 2136 ms 681256 KB Output is correct
80 Correct 3345 ms 903060 KB Output is correct
81 Correct 2016 ms 670612 KB Output is correct
82 Correct 2717 ms 828312 KB Output is correct
83 Correct 3511 ms 930124 KB Output is correct
84 Correct 2097 ms 657460 KB Output is correct
85 Correct 3508 ms 929404 KB Output is correct
86 Correct 3586 ms 913588 KB Output is correct
87 Correct 2682 ms 662344 KB Output is correct
88 Correct 4730 ms 914460 KB Output is correct
89 Correct 4610 ms 914780 KB Output is correct
90 Correct 4692 ms 914716 KB Output is correct