oj.uz

Submission #1034766

# Submission time Handle Problem Language Result Execution time Memory
1034766 2024-07-25T17:37:57 Z tosivanmak Rectangles (IOI19_rect) C++17
72 / 100
 2009 ms 1048576 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[2501][12];
    // 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 n){
        for(int i=1;i<=n;i++){
            stmax[i][0]=arr[i];
        }
        for(int j=1;j<=11;j++){
            for(int i=1;i<=n;i++){
                if(i+(1<<(j-1))<=n){
                    stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
                }
            }
        }
    }
    ll qry(ll ql, ll qr){
        ll rng=lg[qr-ql+1];
        return max(stmax[ql][rng],stmax[qr-(1<<rng)+1][rng]);
    }
};
struct Sparse_Table_Min{
    int stmin[2501][12];
    int arr[2501];
    void init(ll n){
        
    }
    void build(ll n){
        for(int i=1;i<=n;i++){
            stmin[i][0]=arr[i];
        }
        for(int j=1;j<=11;j++){
            for(int i=1;i<=n;i++){
                if(i+(1<<(j-1))<=n){
                    stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
                }
            }
        }
    }
    ll qry(ll ql, ll qr){
        ll rng=lg[qr-ql+1];
        return min(stmin[ql][rng],stmin[qr-(1<<rng)+1][rng]);
    }  
};
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(m),spmax[i].build(m);
    }
    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;
                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);
                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 155220 KB Output is correct
2 Correct 72 ms 156240 KB Output is correct
3 Correct 65 ms 155988 KB Output is correct
4 Correct 63 ms 156216 KB Output is correct
5 Correct 65 ms 156056 KB Output is correct
6 Correct 66 ms 156216 KB Output is correct
7 Correct 66 ms 155988 KB Output is correct
8 Correct 69 ms 155468 KB Output is correct
9 Correct 81 ms 155988 KB Output is correct
10 Correct 64 ms 155984 KB Output is correct
11 Correct 65 ms 155988 KB Output is correct
12 Correct 72 ms 155988 KB Output is correct
13 Correct 65 ms 154968 KB Output is correct
14 Correct 65 ms 154960 KB Output is correct
15 Correct 67 ms 155444 KB Output is correct
16 Correct 64 ms 155220 KB Output is correct
17 Correct 64 ms 154960 KB Output is correct
18 Correct 63 ms 155164 KB Output is correct
19 Correct 64 ms 156196 KB Output is correct
20 Correct 64 ms 156132 KB Output is correct
21 Correct 68 ms 154960 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 155220 KB Output is correct
2 Correct 72 ms 156240 KB Output is correct
3 Correct 65 ms 155988 KB Output is correct
4 Correct 63 ms 156216 KB Output is correct
5 Correct 65 ms 156056 KB Output is correct
6 Correct 66 ms 156216 KB Output is correct
7 Correct 66 ms 155988 KB Output is correct
8 Correct 69 ms 155468 KB Output is correct
9 Correct 81 ms 155988 KB Output is correct
10 Correct 64 ms 155984 KB Output is correct
11 Correct 65 ms 155988 KB Output is correct
12 Correct 72 ms 155988 KB Output is correct
13 Correct 65 ms 154968 KB Output is correct
14 Correct 65 ms 154960 KB Output is correct
15 Correct 67 ms 155444 KB Output is correct
16 Correct 64 ms 155220 KB Output is correct
17 Correct 64 ms 154960 KB Output is correct
18 Correct 63 ms 155164 KB Output is correct
19 Correct 64 ms 156196 KB Output is correct
20 Correct 64 ms 156132 KB Output is correct
21 Correct 68 ms 154960 KB Output is correct
22 Correct 65 ms 158244 KB Output is correct
23 Correct 67 ms 158292 KB Output is correct
24 Correct 66 ms 158288 KB Output is correct
25 Correct 68 ms 158292 KB Output is correct
26 Correct 66 ms 158292 KB Output is correct
27 Correct 70 ms 158256 KB Output is correct
28 Correct 79 ms 158252 KB Output is correct
29 Correct 79 ms 157908 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 155220 KB Output is correct
2 Correct 72 ms 156240 KB Output is correct
3 Correct 65 ms 155988 KB Output is correct
4 Correct 63 ms 156216 KB Output is correct
5 Correct 65 ms 156056 KB Output is correct
6 Correct 66 ms 156216 KB Output is correct
7 Correct 66 ms 155988 KB Output is correct
8 Correct 69 ms 155468 KB Output is correct
9 Correct 81 ms 155988 KB Output is correct
10 Correct 64 ms 155984 KB Output is correct
11 Correct 65 ms 155988 KB Output is correct
12 Correct 72 ms 155988 KB Output is correct
13 Correct 65 ms 154968 KB Output is correct
14 Correct 65 ms 154960 KB Output is correct
15 Correct 67 ms 155444 KB Output is correct
16 Correct 64 ms 155220 KB Output is correct
17 Correct 65 ms 158244 KB Output is correct
18 Correct 67 ms 158292 KB Output is correct
19 Correct 66 ms 158288 KB Output is correct
20 Correct 68 ms 158292 KB Output is correct
21 Correct 66 ms 158292 KB Output is correct
22 Correct 70 ms 158256 KB Output is correct
23 Correct 79 ms 158252 KB Output is correct
24 Correct 79 ms 157908 KB Output is correct
25 Correct 64 ms 154960 KB Output is correct
26 Correct 63 ms 155164 KB Output is correct
27 Correct 64 ms 156196 KB Output is correct
28 Correct 64 ms 156132 KB Output is correct
29 Correct 68 ms 154960 KB Output is correct
30 Correct 78 ms 166352 KB Output is correct
31 Correct 76 ms 166344 KB Output is correct
32 Correct 80 ms 166500 KB Output is correct
33 Correct 76 ms 165968 KB Output is correct
34 Correct 84 ms 166584 KB Output is correct
35 Correct 84 ms 166608 KB Output is correct
36 Correct 82 ms 166352 KB Output is correct
37 Correct 82 ms 166352 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 155220 KB Output is correct
2 Correct 72 ms 156240 KB Output is correct
3 Correct 65 ms 155988 KB Output is correct
4 Correct 63 ms 156216 KB Output is correct
5 Correct 65 ms 156056 KB Output is correct
6 Correct 66 ms 156216 KB Output is correct
7 Correct 66 ms 155988 KB Output is correct
8 Correct 69 ms 155468 KB Output is correct
9 Correct 81 ms 155988 KB Output is correct
10 Correct 64 ms 155984 KB Output is correct
11 Correct 65 ms 155988 KB Output is correct
12 Correct 72 ms 155988 KB Output is correct
13 Correct 65 ms 154968 KB Output is correct
14 Correct 65 ms 154960 KB Output is correct
15 Correct 67 ms 155444 KB Output is correct
16 Correct 64 ms 155220 KB Output is correct
17 Correct 65 ms 158244 KB Output is correct
18 Correct 67 ms 158292 KB Output is correct
19 Correct 66 ms 158288 KB Output is correct
20 Correct 68 ms 158292 KB Output is correct
21 Correct 66 ms 158292 KB Output is correct
22 Correct 70 ms 158256 KB Output is correct
23 Correct 79 ms 158252 KB Output is correct
24 Correct 79 ms 157908 KB Output is correct
25 Correct 78 ms 166352 KB Output is correct
26 Correct 76 ms 166344 KB Output is correct
27 Correct 80 ms 166500 KB Output is correct
28 Correct 76 ms 165968 KB Output is correct
29 Correct 84 ms 166584 KB Output is correct
30 Correct 84 ms 166608 KB Output is correct
31 Correct 82 ms 166352 KB Output is correct
32 Correct 82 ms 166352 KB Output is correct
33 Correct 64 ms 154960 KB Output is correct
34 Correct 63 ms 155164 KB Output is correct
35 Correct 64 ms 156196 KB Output is correct
36 Correct 64 ms 156132 KB Output is correct
37 Correct 68 ms 154960 KB Output is correct
38 Correct 231 ms 245948 KB Output is correct
39 Correct 185 ms 245948 KB Output is correct
40 Correct 226 ms 245948 KB Output is correct
41 Correct 199 ms 245964 KB Output is correct
42 Correct 195 ms 244916 KB Output is correct
43 Correct 203 ms 244856 KB Output is correct
44 Correct 195 ms 244916 KB Output is correct
45 Correct 190 ms 239028 KB Output is correct
46 Correct 184 ms 237004 KB Output is correct
47 Correct 209 ms 238648 KB Output is correct
48 Correct 392 ms 244936 KB Output is correct
49 Correct 351 ms 245196 KB Output is correct
50 Correct 202 ms 210128 KB Output is correct
51 Correct 215 ms 200380 KB Output is correct
52 Correct 315 ms 244152 KB Output is correct
53 Correct 350 ms 244000 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 156276 KB Output is correct
2 Correct 67 ms 156244 KB Output is correct
3 Correct 65 ms 155988 KB Output is correct
4 Correct 64 ms 155000 KB Output is correct
5 Correct 70 ms 156292 KB Output is correct
6 Correct 68 ms 156280 KB Output is correct
7 Correct 67 ms 156244 KB Output is correct
8 Correct 85 ms 156240 KB Output is correct
9 Correct 70 ms 156240 KB Output is correct
10 Correct 70 ms 155220 KB Output is correct
11 Correct 67 ms 155220 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 154960 KB Output is correct
2 Correct 63 ms 155164 KB Output is correct
3 Correct 64 ms 156196 KB Output is correct
4 Correct 64 ms 156132 KB Output is correct
5 Correct 68 ms 154960 KB Output is correct
6 Correct 80 ms 155308 KB Output is correct
7 Correct 763 ms 533328 KB Output is correct
8 Correct 1858 ms 945000 KB Output is correct
9 Correct 1706 ms 949804 KB Output is correct
10 Correct 1627 ms 950028 KB Output is correct
11 Correct 398 ms 529884 KB Output is correct
12 Correct 704 ms 894276 KB Output is correct
13 Correct 740 ms 914000 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 155220 KB Output is correct
2 Correct 72 ms 156240 KB Output is correct
3 Correct 65 ms 155988 KB Output is correct
4 Correct 63 ms 156216 KB Output is correct
5 Correct 65 ms 156056 KB Output is correct
6 Correct 66 ms 156216 KB Output is correct
7 Correct 66 ms 155988 KB Output is correct
8 Correct 69 ms 155468 KB Output is correct
9 Correct 81 ms 155988 KB Output is correct
10 Correct 64 ms 155984 KB Output is correct
11 Correct 65 ms 155988 KB Output is correct
12 Correct 72 ms 155988 KB Output is correct
13 Correct 65 ms 154968 KB Output is correct
14 Correct 65 ms 154960 KB Output is correct
15 Correct 67 ms 155444 KB Output is correct
16 Correct 64 ms 155220 KB Output is correct
17 Correct 65 ms 158244 KB Output is correct
18 Correct 67 ms 158292 KB Output is correct
19 Correct 66 ms 158288 KB Output is correct
20 Correct 68 ms 158292 KB Output is correct
21 Correct 66 ms 158292 KB Output is correct
22 Correct 70 ms 158256 KB Output is correct
23 Correct 79 ms 158252 KB Output is correct
24 Correct 79 ms 157908 KB Output is correct
25 Correct 78 ms 166352 KB Output is correct
26 Correct 76 ms 166344 KB Output is correct
27 Correct 80 ms 166500 KB Output is correct
28 Correct 76 ms 165968 KB Output is correct
29 Correct 84 ms 166584 KB Output is correct
30 Correct 84 ms 166608 KB Output is correct
31 Correct 82 ms 166352 KB Output is correct
32 Correct 82 ms 166352 KB Output is correct
33 Correct 231 ms 245948 KB Output is correct
34 Correct 185 ms 245948 KB Output is correct
35 Correct 226 ms 245948 KB Output is correct
36 Correct 199 ms 245964 KB Output is correct
37 Correct 195 ms 244916 KB Output is correct
38 Correct 203 ms 244856 KB Output is correct
39 Correct 195 ms 244916 KB Output is correct
40 Correct 190 ms 239028 KB Output is correct
41 Correct 184 ms 237004 KB Output is correct
42 Correct 209 ms 238648 KB Output is correct
43 Correct 392 ms 244936 KB Output is correct
44 Correct 351 ms 245196 KB Output is correct
45 Correct 202 ms 210128 KB Output is correct
46 Correct 215 ms 200380 KB Output is correct
47 Correct 315 ms 244152 KB Output is correct
48 Correct 350 ms 244000 KB Output is correct
49 Correct 65 ms 156276 KB Output is correct
50 Correct 67 ms 156244 KB Output is correct
51 Correct 65 ms 155988 KB Output is correct
52 Correct 64 ms 155000 KB Output is correct
53 Correct 70 ms 156292 KB Output is correct
54 Correct 68 ms 156280 KB Output is correct
55 Correct 67 ms 156244 KB Output is correct
56 Correct 85 ms 156240 KB Output is correct
57 Correct 70 ms 156240 KB Output is correct
58 Correct 70 ms 155220 KB Output is correct
59 Correct 67 ms 155220 KB Output is correct
60 Correct 80 ms 155308 KB Output is correct
61 Correct 763 ms 533328 KB Output is correct
62 Correct 1858 ms 945000 KB Output is correct
63 Correct 1706 ms 949804 KB Output is correct
64 Correct 1627 ms 950028 KB Output is correct
65 Correct 398 ms 529884 KB Output is correct
66 Correct 704 ms 894276 KB Output is correct
67 Correct 740 ms 914000 KB Output is correct
68 Correct 64 ms 154960 KB Output is correct
69 Correct 63 ms 155164 KB Output is correct
70 Correct 64 ms 156196 KB Output is correct
71 Correct 64 ms 156132 KB Output is correct
72 Correct 68 ms 154960 KB Output is correct
73 Runtime error 2009 ms 1048576 KB Execution killed with signal 9
74 Halted 0 ms 0 KB -