Submission #1034766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034766		tosivanmak	Rectangles (IOI19_rect)	C++17	72 / 100	2009 ms	1048576 KiB

rect

#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 (stderr)

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 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28