oj.uz

Submission #1034769

# Submission time Handle Problem Language Result Execution time Memory
1034769 2024-07-25T17:45:35 Z tosivanmak Rectangles (IOI19_rect) C++17
100 / 100
 4679 ms 700200 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll lg[1000005];
struct Sparse_Table_Max{
//   vector<vector<int> >stmax;
int stmax[10001];
    // vector<ll>arr;
    int arr[2501];
    void init(ll n){
        // stmax.resize(n+5);
        // for(int i=0;i<n+5;i++){
            // stmax[i].resize(12);
        // }
        // arr.resize(n+5);
    }
    void build(ll l, ll r, ll id){
        if(l==r)stmax[id]=arr[l];
        else{
            ll mid=(l+r)>>1;
            build(l,mid,id*2); build(mid+1,r,id*2+1);
            stmax[id]=max(stmax[id*2],stmax[id*2+1]);
        }
    }
    ll qry(ll ql, ll qr, ll l, ll r, ll id){
        if(l>qr||r<ql){
            return -1e10;
        }
        if(l>=ql&&r<=qr)return stmax[id];
        ll mid=(l+r)>>1;
        return max(qry(ql,qr,l,mid,id*2),qry(ql,qr,mid+1,r,id*2+1));
    }
};
struct Sparse_Table_Min{
    int stmin[10001];
    int arr[2501];
    void init(ll n){
        
    }
    void build(ll l, ll r, ll id){
        if(l==r)stmin[id]=arr[l];
        else{
            ll mid=(l+r)>>1;
            build(l,mid,id*2); build(mid+1,r,id*2+1);
            stmin[id]=min(stmin[id*2],stmin[id*2+1]);
        }
    }
    ll qry(ll ql, ll qr, ll l, ll r, ll id){
        if(l>qr||r<ql){
            return 1e10;
        }
        if(l>=ql&&r<=qr)return stmin[id];
        ll mid=(l+r)>>1;
        return min(qry(ql,qr,l,mid,id*2),qry(ql,qr,mid+1,r,id*2+1));
    }
};
struct Fenwick{
  vector<int>tree;
    void init(ll n){
        tree.resize(n+5,0);
    }
    void upd(ll n, ll m, ll val){
        for(int i=n;i<=m;i+=(i&(-i))){
            tree[i]+=val;
        }
    }
    void reset(ll n, ll m){
        for(int i=n;i<=m;i+=(i&(-i))){
            tree[i]=0;
        }
    }
    ll sum(ll e){
        ll s=0;
        while(e>=1){
            s+=tree[e]; e-=(e&(-e));
        }
        return s;
    }
    ll qry(ll ql, ll qr){
        return sum(qr)-sum(ql-1);
    }
}BIT;
struct Union_Find{
    vector<int>fa,siz,lef,righ;
    void init(ll n){
        fa.resize(n+5),siz.resize(n+5);
        lef.resize(n+5),righ.resize(n+5);
        for(int i=1;i<=n;i++){
            fa[i]=i,siz[i]=1,lef[i]=righ[i]=i;
        }
    }
    ll root(ll x){
        if(fa[x]==x)return x;
        return fa[x]=root(fa[x]);
    }
    void unite(ll u, ll v){
        u=root(u),v=root(v);
        if(siz[u]<siz[v])swap(u,v);
        siz[u]+=siz[v],fa[v]=u;
        lef[u]=min(lef[u],lef[v]);righ[u]=max(righ[u],righ[v]);
    }
    void clear(){
        lef.clear(),righ.clear(),siz.clear(),fa.clear();
    }
}dsu;
Sparse_Table_Min spmin[2505];
Sparse_Table_Max spmax[2505];
ll n,m;
int grid[2501][2501];
int maxi[2501][2501],mini[2501][2501];
vector<pair<int,int> >ope[2501];
vector<int>ele[2501];
vector<pair<int,int> >hv[2501];
vector<pair<int,int> >all;
vector<int>inside[6250005];
void proc(ll id){
    vector<ll>srt;
    for(int i=1;i<=m;i++){
       srt.push_back(grid[id][i]);
    }
    sort(srt.begin(),srt.end());
    srt.erase(unique(srt.begin(),srt.end()),srt.end());
    for(int i=1;i<=m;i++){
        ll it=lower_bound(srt.begin(),srt.end(),grid[id][i])-srt.begin()+1;
        ele[it].push_back(i);
    }
    vector<pair<int,int> >ss;
    dsu.init(m);
    bool merged[m+5];
    for(int i=1;i<=m;i++)merged[i]=0;
    for(int i=1;i<=srt.size();i++){
        for(auto& u: ele[i]){
            if(u!=1){
                if(merged[u-1])dsu.unite(u,u-1);
            }
            if(u!=m){
                if(merged[u+1])dsu.unite(u,u+1);
            }
            merged[u]=1;
        }
        for(auto& u: ele[i]){
            ll f=dsu.root(u);
            ll l=dsu.lef[f],r=dsu.righ[f];
            if(l!=1&&r!=m){
                ss.push_back({l,r});
            }
        }
    }
    sort(ss.begin(),ss.end());
    ss.erase(unique(ss.begin(),ss.end()),ss.end());
    for(int i=1;i<=srt.size();i++)ele[i].clear();
    dsu.clear();
    hv[id]=ss;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	n=a.size(),m=a[0].size();
    for(int i=2;i<=1000000;i*=2){
        lg[i]=1;
    }
    for(int i=3;i<=1000000;i++){
        lg[i]+=lg[i-1];
    }
    if(n<=2||m<=2)return 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            grid[i+1][j+1]=a[i][j];
        }
    }
    for(int i=2;i<n;i++){
        proc(i);
    }
    stack<pair<ll,ll> >sta;
    for(int j=2;j<m;j++){
        for(int i=1;i<=n;i++){
            if(sta.size()==0){
                sta.push({grid[i][j],i});
            }
            else{
                while(sta.size()){
                    ll lol=sta.top().first;
                    if(lol<=grid[i][j]){
                        maxi[sta.top().second][j]=i-1;
                        sta.pop();
                    }
                    else{
                        break;
                    }
                }
                sta.push({grid[i][j],i});
            }
        }
        while(sta.size()){
            maxi[sta.top().second][j]=10000;
            sta.pop();
        }
    }
    for(int j=2;j<m;j++){
        for(int i=n;i>=1;i--){
            if(sta.size()==0){
                sta.push({grid[i][j],i});
            }
            else{
                while(sta.size()){
                    ll lol=sta.top().first;
                    if(lol<=grid[i][j]){
                        mini[sta.top().second][j]=i+1;
                        sta.pop();
                    }
                    else{
                        break;
                    }
                }
                sta.push({grid[i][j],i});
            }
        }
        while(sta.size()){
            mini[sta.top().second][j]=-10000;
            sta.pop();
        }
    }
    for(int i=1;i<=n;i++){
        for(auto& u: hv[i]){
            all.push_back(u);
        }
    }
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());
    for(int i=1;i<=n;i++){
        spmin[i].init(m),spmax[i].init(m);
        for(int j=1;j<=m;j++){
            spmin[i].arr[j]=maxi[i][j];
            spmax[i].arr[j]=mini[i][j];
        }
        spmin[i].build(1,m,1),spmax[i].build(1,m,1);
    }
    for(int i=1;i<=n;i++){
        for(auto& u: hv[i]){
            ll hsh=lower_bound(all.begin(),all.end(),u)-all.begin()+1;
            inside[hsh].push_back(i);
        }
    }
    ll answer=0;
    BIT.init(n);
    ll tot=all.size();
    for(int i=1;i<=tot;i++){
        // cout<<all[i-1].first<<" "<<all[i-1].second<<":\n";
        ll lef=-1;
        vector<pair<int,int> >po;
        for(int j=0;j<inside[i].size();j++){
            // cout<<inside[i][j]<<'\n';
            if(j==0)lef=inside[i][j];
            else{
                if(inside[i][j]!=inside[i][j-1]+1){
                    po.push_back({lef,inside[i][j-1]});
                    lef=inside[i][j];
                }
            }
        }
        po.push_back({lef,inside[i][inside[i].size()-1]});
        for(auto& [l,r]: po){
            // cout<<l<<" "<<r<<'\n';
            for(int j=l-1;j<=r-1;j++){
                ope[j+1].push_back({j,1});
                ll nxt=spmin[j].qry(all[i-1].first,all[i-1].second,1,m,1)+1;
                if(nxt<=r){
                    ope[nxt].push_back({j,-1});
                }
            }
            for(int j=l;j<=r;j++){
                for(auto& k: ope[j]){
                    // cout<<"operation "<<k.first<<" "<<k.second<<'\n';
                    if(k.second==1)BIT.upd(k.first,n,1);
                    else BIT.upd(k.first,n,-1);
                }
                ll go=spmax[j+1].qry(all[i-1].first,all[i-1].second,1,m,1);
                go--;
                go=max(go,1LL);
                answer+=BIT.qry(go,j-1);
            }
            for(int j=l-1;j<=r;j++)BIT.reset(j,n),ope[j].clear();
            // cout<<answer<<'\n';
        }
        
    }
    return answer;
    // return -1;
}

Compilation message

rect.cpp: In function 'void proc(long long int)':
rect.cpp:133:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for(int i=1;i<=srt.size();i++){
      |                 ~^~~~~~~~~~~~
rect.cpp:153:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for(int i=1;i<=srt.size();i++)ele[i].clear();
      |                 ~^~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:251:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |         for(int j=0;j<inside[i].size();j++){
      |                     ~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 155216 KB Output is correct
2 Correct 71 ms 156004 KB Output is correct
3 Correct 82 ms 155988 KB Output is correct
4 Correct 65 ms 155984 KB Output is correct
5 Correct 64 ms 155984 KB Output is correct
6 Correct 64 ms 155984 KB Output is correct
7 Correct 64 ms 155984 KB Output is correct
8 Correct 64 ms 155476 KB Output is correct
9 Correct 65 ms 155992 KB Output is correct
10 Correct 81 ms 155984 KB Output is correct
11 Correct 65 ms 155988 KB Output is correct
12 Correct 63 ms 155984 KB Output is correct
13 Correct 65 ms 154960 KB Output is correct
14 Correct 70 ms 154968 KB Output is correct
15 Correct 65 ms 155476 KB Output is correct
16 Correct 65 ms 155216 KB Output is correct
17 Correct 65 ms 154968 KB Output is correct
18 Correct 64 ms 154964 KB Output is correct
19 Correct 64 ms 155984 KB Output is correct
20 Correct 65 ms 155984 KB Output is correct
21 Correct 62 ms 154960 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 155216 KB Output is correct
2 Correct 71 ms 156004 KB Output is correct
3 Correct 82 ms 155988 KB Output is correct
4 Correct 65 ms 155984 KB Output is correct
5 Correct 64 ms 155984 KB Output is correct
6 Correct 64 ms 155984 KB Output is correct
7 Correct 64 ms 155984 KB Output is correct
8 Correct 64 ms 155476 KB Output is correct
9 Correct 65 ms 155992 KB Output is correct
10 Correct 81 ms 155984 KB Output is correct
11 Correct 65 ms 155988 KB Output is correct
12 Correct 63 ms 155984 KB Output is correct
13 Correct 65 ms 154960 KB Output is correct
14 Correct 70 ms 154968 KB Output is correct
15 Correct 65 ms 155476 KB Output is correct
16 Correct 65 ms 155216 KB Output is correct
17 Correct 65 ms 154968 KB Output is correct
18 Correct 64 ms 154964 KB Output is correct
19 Correct 64 ms 155984 KB Output is correct
20 Correct 65 ms 155984 KB Output is correct
21 Correct 62 ms 154960 KB Output is correct
22 Correct 84 ms 157788 KB Output is correct
23 Correct 72 ms 157780 KB Output is correct
24 Correct 69 ms 157784 KB Output is correct
25 Correct 66 ms 157776 KB Output is correct
26 Correct 67 ms 157696 KB Output is correct
27 Correct 74 ms 158032 KB Output is correct
28 Correct 81 ms 157856 KB Output is correct
29 Correct 66 ms 157520 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 155216 KB Output is correct
2 Correct 71 ms 156004 KB Output is correct
3 Correct 82 ms 155988 KB Output is correct
4 Correct 65 ms 155984 KB Output is correct
5 Correct 64 ms 155984 KB Output is correct
6 Correct 64 ms 155984 KB Output is correct
7 Correct 64 ms 155984 KB Output is correct
8 Correct 64 ms 155476 KB Output is correct
9 Correct 65 ms 155992 KB Output is correct
10 Correct 81 ms 155984 KB Output is correct
11 Correct 65 ms 155988 KB Output is correct
12 Correct 63 ms 155984 KB Output is correct
13 Correct 65 ms 154960 KB Output is correct
14 Correct 70 ms 154968 KB Output is correct
15 Correct 65 ms 155476 KB Output is correct
16 Correct 65 ms 155216 KB Output is correct
17 Correct 84 ms 157788 KB Output is correct
18 Correct 72 ms 157780 KB Output is correct
19 Correct 69 ms 157784 KB Output is correct
20 Correct 66 ms 157776 KB Output is correct
21 Correct 67 ms 157696 KB Output is correct
22 Correct 74 ms 158032 KB Output is correct
23 Correct 81 ms 157856 KB Output is correct
24 Correct 66 ms 157520 KB Output is correct
25 Correct 65 ms 154968 KB Output is correct
26 Correct 64 ms 154964 KB Output is correct
27 Correct 64 ms 155984 KB Output is correct
28 Correct 65 ms 155984 KB Output is correct
29 Correct 62 ms 154960 KB Output is correct
30 Correct 79 ms 163536 KB Output is correct
31 Correct 83 ms 163512 KB Output is correct
32 Correct 77 ms 163536 KB Output is correct
33 Correct 73 ms 162900 KB Output is correct
34 Correct 86 ms 163536 KB Output is correct
35 Correct 86 ms 163536 KB Output is correct
36 Correct 84 ms 163536 KB Output is correct
37 Correct 84 ms 163320 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 155216 KB Output is correct
2 Correct 71 ms 156004 KB Output is correct
3 Correct 82 ms 155988 KB Output is correct
4 Correct 65 ms 155984 KB Output is correct
5 Correct 64 ms 155984 KB Output is correct
6 Correct 64 ms 155984 KB Output is correct
7 Correct 64 ms 155984 KB Output is correct
8 Correct 64 ms 155476 KB Output is correct
9 Correct 65 ms 155992 KB Output is correct
10 Correct 81 ms 155984 KB Output is correct
11 Correct 65 ms 155988 KB Output is correct
12 Correct 63 ms 155984 KB Output is correct
13 Correct 65 ms 154960 KB Output is correct
14 Correct 70 ms 154968 KB Output is correct
15 Correct 65 ms 155476 KB Output is correct
16 Correct 65 ms 155216 KB Output is correct
17 Correct 84 ms 157788 KB Output is correct
18 Correct 72 ms 157780 KB Output is correct
19 Correct 69 ms 157784 KB Output is correct
20 Correct 66 ms 157776 KB Output is correct
21 Correct 67 ms 157696 KB Output is correct
22 Correct 74 ms 158032 KB Output is correct
23 Correct 81 ms 157856 KB Output is correct
24 Correct 66 ms 157520 KB Output is correct
25 Correct 79 ms 163536 KB Output is correct
26 Correct 83 ms 163512 KB Output is correct
27 Correct 77 ms 163536 KB Output is correct
28 Correct 73 ms 162900 KB Output is correct
29 Correct 86 ms 163536 KB Output is correct
30 Correct 86 ms 163536 KB Output is correct
31 Correct 84 ms 163536 KB Output is correct
32 Correct 84 ms 163320 KB Output is correct
33 Correct 65 ms 154968 KB Output is correct
34 Correct 64 ms 154964 KB Output is correct
35 Correct 64 ms 155984 KB Output is correct
36 Correct 65 ms 155984 KB Output is correct
37 Correct 62 ms 154960 KB Output is correct
38 Correct 306 ms 210876 KB Output is correct
39 Correct 232 ms 210876 KB Output is correct
40 Correct 258 ms 210860 KB Output is correct
41 Correct 216 ms 211168 KB Output is correct
42 Correct 247 ms 209968 KB Output is correct
43 Correct 246 ms 209844 KB Output is correct
44 Correct 247 ms 210104 KB Output is correct
45 Correct 234 ms 206636 KB Output is correct
46 Correct 168 ms 202188 KB Output is correct
47 Correct 205 ms 203800 KB Output is correct
48 Correct 348 ms 210124 KB Output is correct
49 Correct 360 ms 210656 KB Output is correct
50 Correct 199 ms 192504 KB Output is correct
51 Correct 230 ms 182976 KB Output is correct
52 Correct 321 ms 209112 KB Output is correct
53 Correct 365 ms 209356 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 155728 KB Output is correct
2 Correct 65 ms 155728 KB Output is correct
3 Correct 68 ms 155732 KB Output is correct
4 Correct 64 ms 155180 KB Output is correct
5 Correct 68 ms 155788 KB Output is correct
6 Correct 77 ms 155820 KB Output is correct
7 Correct 68 ms 155732 KB Output is correct
8 Correct 66 ms 155728 KB Output is correct
9 Correct 67 ms 155732 KB Output is correct
10 Correct 67 ms 155220 KB Output is correct
11 Correct 64 ms 155008 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 154968 KB Output is correct
2 Correct 64 ms 154964 KB Output is correct
3 Correct 64 ms 155984 KB Output is correct
4 Correct 65 ms 155984 KB Output is correct
5 Correct 62 ms 154960 KB Output is correct
6 Correct 63 ms 155460 KB Output is correct
7 Correct 737 ms 343236 KB Output is correct
8 Correct 1511 ms 540092 KB Output is correct
9 Correct 1518 ms 541816 KB Output is correct
10 Correct 1449 ms 541784 KB Output is correct
11 Correct 345 ms 328784 KB Output is correct
12 Correct 625 ms 503772 KB Output is correct
13 Correct 645 ms 506960 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 155216 KB Output is correct
2 Correct 71 ms 156004 KB Output is correct
3 Correct 82 ms 155988 KB Output is correct
4 Correct 65 ms 155984 KB Output is correct
5 Correct 64 ms 155984 KB Output is correct
6 Correct 64 ms 155984 KB Output is correct
7 Correct 64 ms 155984 KB Output is correct
8 Correct 64 ms 155476 KB Output is correct
9 Correct 65 ms 155992 KB Output is correct
10 Correct 81 ms 155984 KB Output is correct
11 Correct 65 ms 155988 KB Output is correct
12 Correct 63 ms 155984 KB Output is correct
13 Correct 65 ms 154960 KB Output is correct
14 Correct 70 ms 154968 KB Output is correct
15 Correct 65 ms 155476 KB Output is correct
16 Correct 65 ms 155216 KB Output is correct
17 Correct 84 ms 157788 KB Output is correct
18 Correct 72 ms 157780 KB Output is correct
19 Correct 69 ms 157784 KB Output is correct
20 Correct 66 ms 157776 KB Output is correct
21 Correct 67 ms 157696 KB Output is correct
22 Correct 74 ms 158032 KB Output is correct
23 Correct 81 ms 157856 KB Output is correct
24 Correct 66 ms 157520 KB Output is correct
25 Correct 79 ms 163536 KB Output is correct
26 Correct 83 ms 163512 KB Output is correct
27 Correct 77 ms 163536 KB Output is correct
28 Correct 73 ms 162900 KB Output is correct
29 Correct 86 ms 163536 KB Output is correct
30 Correct 86 ms 163536 KB Output is correct
31 Correct 84 ms 163536 KB Output is correct
32 Correct 84 ms 163320 KB Output is correct
33 Correct 306 ms 210876 KB Output is correct
34 Correct 232 ms 210876 KB Output is correct
35 Correct 258 ms 210860 KB Output is correct
36 Correct 216 ms 211168 KB Output is correct
37 Correct 247 ms 209968 KB Output is correct
38 Correct 246 ms 209844 KB Output is correct
39 Correct 247 ms 210104 KB Output is correct
40 Correct 234 ms 206636 KB Output is correct
41 Correct 168 ms 202188 KB Output is correct
42 Correct 205 ms 203800 KB Output is correct
43 Correct 348 ms 210124 KB Output is correct
44 Correct 360 ms 210656 KB Output is correct
45 Correct 199 ms 192504 KB Output is correct
46 Correct 230 ms 182976 KB Output is correct
47 Correct 321 ms 209112 KB Output is correct
48 Correct 365 ms 209356 KB Output is correct
49 Correct 65 ms 155728 KB Output is correct
50 Correct 65 ms 155728 KB Output is correct
51 Correct 68 ms 155732 KB Output is correct
52 Correct 64 ms 155180 KB Output is correct
53 Correct 68 ms 155788 KB Output is correct
54 Correct 77 ms 155820 KB Output is correct
55 Correct 68 ms 155732 KB Output is correct
56 Correct 66 ms 155728 KB Output is correct
57 Correct 67 ms 155732 KB Output is correct
58 Correct 67 ms 155220 KB Output is correct
59 Correct 64 ms 155008 KB Output is correct
60 Correct 63 ms 155460 KB Output is correct
61 Correct 737 ms 343236 KB Output is correct
62 Correct 1511 ms 540092 KB Output is correct
63 Correct 1518 ms 541816 KB Output is correct
64 Correct 1449 ms 541784 KB Output is correct
65 Correct 345 ms 328784 KB Output is correct
66 Correct 625 ms 503772 KB Output is correct
67 Correct 645 ms 506960 KB Output is correct
68 Correct 65 ms 154968 KB Output is correct
69 Correct 64 ms 154964 KB Output is correct
70 Correct 64 ms 155984 KB Output is correct
71 Correct 65 ms 155984 KB Output is correct
72 Correct 62 ms 154960 KB Output is correct
73 Correct 3153 ms 700040 KB Output is correct
74 Correct 2080 ms 700032 KB Output is correct
75 Correct 3082 ms 700016 KB Output is correct
76 Correct 2011 ms 700200 KB Output is correct
77 Correct 3116 ms 689948 KB Output is correct
78 Correct 2386 ms 461276 KB Output is correct
79 Correct 2751 ms 515928 KB Output is correct
80 Correct 4345 ms 662384 KB Output is correct
81 Correct 2680 ms 478168 KB Output is correct
82 Correct 3714 ms 563524 KB Output is correct
83 Correct 4679 ms 690120 KB Output is correct
84 Correct 2423 ms 461840 KB Output is correct
85 Correct 4057 ms 679540 KB Output is correct
86 Correct 3816 ms 664792 KB Output is correct
87 Correct 1952 ms 517240 KB Output is correct
88 Correct 3386 ms 689380 KB Output is correct
89 Correct 3672 ms 689876 KB Output is correct
90 Correct 3633 ms 689868 KB Output is correct