oj.uz

Submission #875905

# Submission time Handle Problem Language Result Execution time Memory
875905 2023-11-20T17:50:01 Z andrei_boaca Rectangles (IOI19_rect) C++17
100 / 100
 2181 ms 423036 KB 
#include "rect.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
int v[2505][2505],n,m,up[2505][2505],down[2505][2505],rmq[15][2505],rdown[15][2505],rup[15][2505],loga[2505],dlin[2505],ulin[2505],valmax[2505];
vector<int> who[2505];
int good[2505],last[2505];
int plin[2505][2505],pcol[2505][2505],s[2505][2505];
int aib[2505];
ll ans;
struct date
{
    int poz,up,down;
};
vector<date> lins[2505][2505];
int lft[2505],rgt[2505];
int getmax(int l,int r)
{
    int lg=loga[r-l+1];
    return max(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
int getup(int l,int r)
{
    int lg=loga[r-l+1];
    return max(rup[lg][l],rup[lg][r-(1<<lg)+1]);
}
int getdown(int l,int r)
{
    int lg=loga[r-l+1];
    return min(rdown[lg][l],rdown[lg][r-(1<<lg)+1]);
}
int lsb(int x)
{
    return x&(-x);
}
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}
int suma(int poz)
{
    int rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
bool comp(date a, date b)
{
    return a.up<b.up;
}
bool bypoz(date a, date b)
{
    return a.poz<b.poz;
}
void calc(vector<date> a)
{
    vector<date> aux=a;
    sort(aux.begin(),aux.end(),comp);
    reverse(aux.begin(),aux.end());
    sort(a.begin(),a.end(),bypoz);
    vector<int> toerase;
    for(int i=0;i<a.size();i++)
    {
        while(!aux.empty()&&aux.back().up<=a[i].poz)
        {
            update(aux.back().poz,1);
            toerase.push_back(aux.back().poz);
            aux.pop_back();
        }
        int l=a[i].poz;
        int r=min(a[i].down,a.back().poz);
        if(l<=r)
            ans+=suma(r)-suma(l-1);
    }
    for(int i:toerase)
        update(i,-1);
}
long long count_rectangles(vector<vector<int>> A)
{
    n=A.size();
    m=A[0].size();
    for(int i=1;i<=2500;i++)
    {
        for(int bit=0;bit<=13;bit++)
            if((1<<bit)<=i)
                loga[i]=bit;
    }
    if(n<=2||m<=2)
        return 0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            v[i][j]=A[i-1][j-1];
    for(int j=1;j<=m;j++)
    {
        for(int i=n;i>=1;i--)
        {
            rmq[0][i]=v[i][j];
            for(int k=1;k<=13;k++)
            {
                rmq[k][i]=rmq[k-1][i];
                int poz=i+(1<<(k-1));
                if(poz<=n)
                    rmq[k][i]=max(rmq[k][i],rmq[k-1][poz]);
            }
        }
        for(int i=2;i<n;i++)
        {
            up[i][j]=1e9;
            down[i][j]=0;
            int st=i;
            int dr=n-1;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(getmax(i,mij)<v[i-1][j])
                {
                    down[i][j]=mij;
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
            st=2;
            dr=i;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(getmax(mij,i)<v[i+1][j])
                {
                    up[i][j]=mij;
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
        }
    }
    for(int i=2;i<n;i++)
    {
        for(int j=m;j>=1;j--)
        {
            lft[j]=0;
            rgt[j]=m+1;
            rup[0][j]=up[i][j];
            rdown[0][j]=down[i][j];
            for(int k=1;k<=13;k++)
            {
                rup[k][j]=rup[k-1][j];
                rdown[k][j]=rdown[k-1][j];
                int poz=j+(1<<(k-1));
                if(poz<=m)
                {
                    rup[k][j]=max(rup[k][j],rup[k-1][poz]);
                    rdown[k][j]=min(rdown[k][j],rdown[k-1][poz]);
                }
            }
        }
        deque<int> coada;
        for(int j=1;j<=m;j++)
        {
            while(!coada.empty()&&v[i][j]>=v[i][coada.back()])
                coada.pop_back();
            if(coada.empty())
                lft[j]=0;
            else
                lft[j]=coada.back()+1;
            coada.push_back(j);
        }
        coada.clear();
        for(int j=m;j>=1;j--)
        {
            while(!coada.empty()&&v[i][j]>=v[i][coada.back()])
                coada.pop_back();
            if(coada.empty())
                rgt[j]=m+1;
            else
                rgt[j]=coada.back()-1;
            coada.push_back(j);
        }
        for(int j=1;j<=m;j++)
        {
            int l=lft[j],r=rgt[j];
            if(l>=2&&r<=m-1&&l<=r)
                lins[l][r].push_back({i,getup(l,r),getdown(l,r)});
        }
    }
    for(int c1=2;c1<m;c1++)
        for(int c2=c1;c2<m;c2++)
            if(lins[c1][c2].size()>=1)
            {
                vector<date> a=lins[c1][c2];
                sort(a.begin(),a.end(),bypoz);
                vector<date> vals;
                for(int i=0;i<a.size();i++)
                {
                    if(i>0&&a[i].poz==a[i-1].poz)
                        continue;
                    if(i==0||a[i].poz==a[i-1].poz+1)
                        vals.push_back(a[i]);
                    else
                    {
                        calc(vals);
                        vals.clear();
                        vals.push_back(a[i]);
                    }
                }
                if(!vals.empty())
                    calc(vals);
            }
    return ans;
}

Compilation message

rect.cpp: In function 'void calc(std::vector<date>)':
rect.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<date>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<a.size();i++)
      |                 ~^~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:196:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<date>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |                 for(int i=0;i<a.size();i++)
      |                             ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 154268 KB Output is correct
2 Correct 32 ms 160556 KB Output is correct
3 Correct 33 ms 160856 KB Output is correct
4 Correct 32 ms 160604 KB Output is correct
5 Correct 32 ms 160600 KB Output is correct
6 Correct 33 ms 160588 KB Output is correct
7 Correct 32 ms 160600 KB Output is correct
8 Correct 31 ms 154448 KB Output is correct
9 Correct 32 ms 161116 KB Output is correct
10 Correct 32 ms 160564 KB Output is correct
11 Correct 33 ms 160596 KB Output is correct
12 Correct 33 ms 160604 KB Output is correct
13 Correct 33 ms 152668 KB Output is correct
14 Correct 31 ms 152400 KB Output is correct
15 Correct 35 ms 154456 KB Output is correct
16 Correct 35 ms 154456 KB Output is correct
17 Correct 31 ms 152404 KB Output is correct
18 Correct 31 ms 152412 KB Output is correct
19 Correct 33 ms 160604 KB Output is correct
20 Correct 32 ms 160604 KB Output is correct
21 Correct 32 ms 152408 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 154268 KB Output is correct
2 Correct 32 ms 160556 KB Output is correct
3 Correct 33 ms 160856 KB Output is correct
4 Correct 32 ms 160604 KB Output is correct
5 Correct 32 ms 160600 KB Output is correct
6 Correct 33 ms 160588 KB Output is correct
7 Correct 32 ms 160600 KB Output is correct
8 Correct 31 ms 154448 KB Output is correct
9 Correct 32 ms 161116 KB Output is correct
10 Correct 32 ms 160564 KB Output is correct
11 Correct 33 ms 160596 KB Output is correct
12 Correct 33 ms 160604 KB Output is correct
13 Correct 33 ms 152668 KB Output is correct
14 Correct 31 ms 152400 KB Output is correct
15 Correct 35 ms 154456 KB Output is correct
16 Correct 35 ms 154456 KB Output is correct
17 Correct 31 ms 152404 KB Output is correct
18 Correct 31 ms 152412 KB Output is correct
19 Correct 33 ms 160604 KB Output is correct
20 Correct 32 ms 160604 KB Output is correct
21 Correct 32 ms 152408 KB Output is correct
22 Correct 34 ms 160844 KB Output is correct
23 Correct 34 ms 160892 KB Output is correct
24 Correct 35 ms 160832 KB Output is correct
25 Correct 35 ms 160604 KB Output is correct
26 Correct 35 ms 160596 KB Output is correct
27 Correct 34 ms 160588 KB Output is correct
28 Correct 36 ms 160596 KB Output is correct
29 Correct 34 ms 160604 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 154268 KB Output is correct
2 Correct 32 ms 160556 KB Output is correct
3 Correct 33 ms 160856 KB Output is correct
4 Correct 32 ms 160604 KB Output is correct
5 Correct 32 ms 160600 KB Output is correct
6 Correct 33 ms 160588 KB Output is correct
7 Correct 32 ms 160600 KB Output is correct
8 Correct 31 ms 154448 KB Output is correct
9 Correct 32 ms 161116 KB Output is correct
10 Correct 32 ms 160564 KB Output is correct
11 Correct 33 ms 160596 KB Output is correct
12 Correct 33 ms 160604 KB Output is correct
13 Correct 33 ms 152668 KB Output is correct
14 Correct 31 ms 152400 KB Output is correct
15 Correct 35 ms 154456 KB Output is correct
16 Correct 35 ms 154456 KB Output is correct
17 Correct 34 ms 160844 KB Output is correct
18 Correct 34 ms 160892 KB Output is correct
19 Correct 35 ms 160832 KB Output is correct
20 Correct 35 ms 160604 KB Output is correct
21 Correct 35 ms 160596 KB Output is correct
22 Correct 34 ms 160588 KB Output is correct
23 Correct 36 ms 160596 KB Output is correct
24 Correct 34 ms 160604 KB Output is correct
25 Correct 31 ms 152404 KB Output is correct
26 Correct 31 ms 152412 KB Output is correct
27 Correct 33 ms 160604 KB Output is correct
28 Correct 32 ms 160604 KB Output is correct
29 Correct 32 ms 152408 KB Output is correct
30 Correct 41 ms 161640 KB Output is correct
31 Correct 41 ms 161960 KB Output is correct
32 Correct 41 ms 161876 KB Output is correct
33 Correct 40 ms 161332 KB Output is correct
34 Correct 44 ms 161616 KB Output is correct
35 Correct 44 ms 161872 KB Output is correct
36 Correct 43 ms 161872 KB Output is correct
37 Correct 43 ms 161868 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 154268 KB Output is correct
2 Correct 32 ms 160556 KB Output is correct
3 Correct 33 ms 160856 KB Output is correct
4 Correct 32 ms 160604 KB Output is correct
5 Correct 32 ms 160600 KB Output is correct
6 Correct 33 ms 160588 KB Output is correct
7 Correct 32 ms 160600 KB Output is correct
8 Correct 31 ms 154448 KB Output is correct
9 Correct 32 ms 161116 KB Output is correct
10 Correct 32 ms 160564 KB Output is correct
11 Correct 33 ms 160596 KB Output is correct
12 Correct 33 ms 160604 KB Output is correct
13 Correct 33 ms 152668 KB Output is correct
14 Correct 31 ms 152400 KB Output is correct
15 Correct 35 ms 154456 KB Output is correct
16 Correct 35 ms 154456 KB Output is correct
17 Correct 34 ms 160844 KB Output is correct
18 Correct 34 ms 160892 KB Output is correct
19 Correct 35 ms 160832 KB Output is correct
20 Correct 35 ms 160604 KB Output is correct
21 Correct 35 ms 160596 KB Output is correct
22 Correct 34 ms 160588 KB Output is correct
23 Correct 36 ms 160596 KB Output is correct
24 Correct 34 ms 160604 KB Output is correct
25 Correct 41 ms 161640 KB Output is correct
26 Correct 41 ms 161960 KB Output is correct
27 Correct 41 ms 161876 KB Output is correct
28 Correct 40 ms 161332 KB Output is correct
29 Correct 44 ms 161616 KB Output is correct
30 Correct 44 ms 161872 KB Output is correct
31 Correct 43 ms 161872 KB Output is correct
32 Correct 43 ms 161868 KB Output is correct
33 Correct 31 ms 152404 KB Output is correct
34 Correct 31 ms 152412 KB Output is correct
35 Correct 33 ms 160604 KB Output is correct
36 Correct 32 ms 160604 KB Output is correct
37 Correct 32 ms 152408 KB Output is correct
38 Correct 141 ms 192244 KB Output is correct
39 Correct 134 ms 192244 KB Output is correct
40 Correct 136 ms 192396 KB Output is correct
41 Correct 133 ms 192456 KB Output is correct
42 Correct 143 ms 193064 KB Output is correct
43 Correct 144 ms 193104 KB Output is correct
44 Correct 146 ms 193476 KB Output is correct
45 Correct 139 ms 191132 KB Output is correct
46 Correct 113 ms 188380 KB Output is correct
47 Correct 128 ms 189380 KB Output is correct
48 Correct 169 ms 191572 KB Output is correct
49 Correct 174 ms 192848 KB Output is correct
50 Correct 104 ms 186180 KB Output is correct
51 Correct 102 ms 173904 KB Output is correct
52 Correct 167 ms 192472 KB Output is correct
53 Correct 168 ms 192720 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 154448 KB Output is correct
2 Correct 38 ms 154448 KB Output is correct
3 Correct 39 ms 154448 KB Output is correct
4 Correct 31 ms 152408 KB Output is correct
5 Correct 42 ms 154568 KB Output is correct
6 Correct 39 ms 154452 KB Output is correct
7 Correct 39 ms 154568 KB Output is correct
8 Correct 40 ms 154460 KB Output is correct
9 Correct 42 ms 154716 KB Output is correct
10 Correct 31 ms 152276 KB Output is correct
11 Correct 31 ms 152400 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 152404 KB Output is correct
2 Correct 31 ms 152412 KB Output is correct
3 Correct 33 ms 160604 KB Output is correct
4 Correct 32 ms 160604 KB Output is correct
5 Correct 32 ms 152408 KB Output is correct
6 Correct 32 ms 154452 KB Output is correct
7 Correct 533 ms 243188 KB Output is correct
8 Correct 1172 ms 340408 KB Output is correct
9 Correct 1161 ms 341308 KB Output is correct
10 Correct 1160 ms 340748 KB Output is correct
11 Correct 364 ms 218964 KB Output is correct
12 Correct 730 ms 275656 KB Output is correct
13 Correct 770 ms 279360 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 154268 KB Output is correct
2 Correct 32 ms 160556 KB Output is correct
3 Correct 33 ms 160856 KB Output is correct
4 Correct 32 ms 160604 KB Output is correct
5 Correct 32 ms 160600 KB Output is correct
6 Correct 33 ms 160588 KB Output is correct
7 Correct 32 ms 160600 KB Output is correct
8 Correct 31 ms 154448 KB Output is correct
9 Correct 32 ms 161116 KB Output is correct
10 Correct 32 ms 160564 KB Output is correct
11 Correct 33 ms 160596 KB Output is correct
12 Correct 33 ms 160604 KB Output is correct
13 Correct 33 ms 152668 KB Output is correct
14 Correct 31 ms 152400 KB Output is correct
15 Correct 35 ms 154456 KB Output is correct
16 Correct 35 ms 154456 KB Output is correct
17 Correct 34 ms 160844 KB Output is correct
18 Correct 34 ms 160892 KB Output is correct
19 Correct 35 ms 160832 KB Output is correct
20 Correct 35 ms 160604 KB Output is correct
21 Correct 35 ms 160596 KB Output is correct
22 Correct 34 ms 160588 KB Output is correct
23 Correct 36 ms 160596 KB Output is correct
24 Correct 34 ms 160604 KB Output is correct
25 Correct 41 ms 161640 KB Output is correct
26 Correct 41 ms 161960 KB Output is correct
27 Correct 41 ms 161876 KB Output is correct
28 Correct 40 ms 161332 KB Output is correct
29 Correct 44 ms 161616 KB Output is correct
30 Correct 44 ms 161872 KB Output is correct
31 Correct 43 ms 161872 KB Output is correct
32 Correct 43 ms 161868 KB Output is correct
33 Correct 141 ms 192244 KB Output is correct
34 Correct 134 ms 192244 KB Output is correct
35 Correct 136 ms 192396 KB Output is correct
36 Correct 133 ms 192456 KB Output is correct
37 Correct 143 ms 193064 KB Output is correct
38 Correct 144 ms 193104 KB Output is correct
39 Correct 146 ms 193476 KB Output is correct
40 Correct 139 ms 191132 KB Output is correct
41 Correct 113 ms 188380 KB Output is correct
42 Correct 128 ms 189380 KB Output is correct
43 Correct 169 ms 191572 KB Output is correct
44 Correct 174 ms 192848 KB Output is correct
45 Correct 104 ms 186180 KB Output is correct
46 Correct 102 ms 173904 KB Output is correct
47 Correct 167 ms 192472 KB Output is correct
48 Correct 168 ms 192720 KB Output is correct
49 Correct 39 ms 154448 KB Output is correct
50 Correct 38 ms 154448 KB Output is correct
51 Correct 39 ms 154448 KB Output is correct
52 Correct 31 ms 152408 KB Output is correct
53 Correct 42 ms 154568 KB Output is correct
54 Correct 39 ms 154452 KB Output is correct
55 Correct 39 ms 154568 KB Output is correct
56 Correct 40 ms 154460 KB Output is correct
57 Correct 42 ms 154716 KB Output is correct
58 Correct 31 ms 152276 KB Output is correct
59 Correct 31 ms 152400 KB Output is correct
60 Correct 32 ms 154452 KB Output is correct
61 Correct 533 ms 243188 KB Output is correct
62 Correct 1172 ms 340408 KB Output is correct
63 Correct 1161 ms 341308 KB Output is correct
64 Correct 1160 ms 340748 KB Output is correct
65 Correct 364 ms 218964 KB Output is correct
66 Correct 730 ms 275656 KB Output is correct
67 Correct 770 ms 279360 KB Output is correct
68 Correct 31 ms 152404 KB Output is correct
69 Correct 31 ms 152412 KB Output is correct
70 Correct 33 ms 160604 KB Output is correct
71 Correct 32 ms 160604 KB Output is correct
72 Correct 32 ms 152408 KB Output is correct
73 Correct 1552 ms 394348 KB Output is correct
74 Correct 1414 ms 417504 KB Output is correct
75 Correct 1670 ms 417516 KB Output is correct
76 Correct 1420 ms 417268 KB Output is correct
77 Correct 1781 ms 423008 KB Output is correct
78 Correct 1183 ms 308816 KB Output is correct
79 Correct 1277 ms 339440 KB Output is correct
80 Correct 2057 ms 394696 KB Output is correct
81 Correct 1253 ms 324460 KB Output is correct
82 Correct 1743 ms 381420 KB Output is correct
83 Correct 2181 ms 420628 KB Output is correct
84 Correct 1142 ms 314116 KB Output is correct
85 Correct 2029 ms 423036 KB Output is correct
86 Correct 1962 ms 417908 KB Output is correct
87 Correct 1069 ms 343476 KB Output is correct
88 Correct 1780 ms 422656 KB Output is correct
89 Correct 1856 ms 422928 KB Output is correct
90 Correct 1814 ms 423000 KB Output is correct