Submission #1063025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063025		Ahmed57	Rectangles (IOI19_rect)	C++17	0 / 100	2 ms	860 KiB

rect

#include "bits/stdc++.h"
using namespace std;
int seg[800001];
void build(int p,int l,int r){
    if(l==r){
        seg[p] = 0;
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
void update(int p,int l,int r,int idx,int val){
    if(l==r){
        seg[p]=max(seg[p],val);
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)update(p*2,l,md,idx,val);
    else update(p*2+1,md+1,r,idx,val);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
int query(int p,int l,int r,int lq,int rq){
    if(r<lq||l>rq||lq>rq)return 1e9;
    if(l>=lq&&r<=rq)return seg[p];
    int md = (l+r)/2;
    return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
long long count_rectangles(vector<vector<int>> a){
    int n = a.size();
    int m = a[0].size();
    vector<pair<int,int>> rngr[n+1],rngc[n+1];
    for(int i = 0;i<n;i++){
        stack<int> st;
        for(int j = 0;j<m;j++){
            while(!st.empty()&&a[i][st.top()]<a[i][j]){
                if(st.top()+1<=j-1){
                rngr[i].push_back({st.top(),j});
                }
                st.pop();
            }
            if(st.size()){
                if(st.top()+1<=j-1){
                rngr[i].push_back({st.top(),j});
                }
            }
            st.push(j);
        }
        sort(rngr[i].begin(),rngr[i].end());
    }
    for(int j = 0;j<m;j++){
        stack<int> st;
        for(int i = 0;i<n;i++){
            while(!st.empty()&&a[st.top()][j]<a[i][j]){
                if(st.top()+1<=i-1){
                rngc[j].push_back({st.top(),i});
                }
                st.pop();
            }
            if(st.size()){
                if(st.top()+1<=i-1){
                rngc[j].push_back({st.top(),i});
                }
            }
            st.push(i);
        }
        sort(rngc[j].begin(),rngc[j].end());
    }
    vector<int> rows[n+1];
    vector<pair<int,int>> cols[n+1];
    for(int i = n-1;i>=0;i--){
        for(int j = 0;j<rngr[i].size();j++){
            int it = lower_bound(rngr[i+1].begin(),rngr[i+1].end(),make_pair(rngr[i][j].first,rngr[i][j].second))-rngr[i+1].begin();
            if(it<rngr[i+1].size()&&rngr[i+1][it]==rngr[i][j]){
                rows[i].push_back(rows[i+1][it]);
            }else{
                rows[i].push_back(i);
            }
        }
    }
    // for(int i = 0;i<n;i++){
    //     for(auto j:rngr[i]){
    //         cout<<j.first<<" "<<j.second<<endl;
    //     }
    //     cout<<"---------------------"<<endl;
    // }
    long long all = 0;
    int col[m] = {0};
    for(int i = 0;i<n;i++){
        int idx = (int)(rngr[i].size())-1;
        vector<pair<int,int>> lol[m];
        for(int j = 0;j<m;j++){
            while(col[j]<rngc[j].size()&&rngc[j][col[j]].first<i){
                lol[j].push_back({rngc[j][col[j]].second,0});
                col[j]++;
            }
            sort(lol[j].begin(),lol[j].end());
        }
        vector<array<int,3>> rng[n+1]; 
        for(int j = 0;j<m;j++){
            for(int e = 0;e<lol[j].size();e++){
                if(lol[j][e].second)continue;
                int st = j;
                while(1){
                    if(st==m){
                        st--;
                        break;
                    }
                    int it = lower_bound(lol[st].begin(),lol[st].end(),make_pair(lol[j][e].first,0))-lol[st].begin();
                    if(it<lol[st].size()&&lol[st][it].first==lol[j][e].first){
                        lol[st][it].second = 1;
                        st++;
                    }else{
                        st--;
                        break;
                    }
                }
                rng[st].push_back({st,lol[j][e].first,1});
                if(j)rng[j-1].push_back({st,lol[j][e].first,0});
            }
        }
        reverse(rngr[i].begin(),rngr[i].end());
        int cur = m-1;
        multiset<pair<int,int>> s;
        for(auto j:rngr[i]){
            int la = rows[i][idx--];
            //cout<<j.first<<" "<<j.second<<" "<<la<<" "<<i<<endl;
            while(cur>j.first){
                for(auto e:rng[cur]){
                    if(e[2]==1)s.insert({e[0],e[1]});
                    else s.erase(s.lower_bound(make_pair(e[0],e[1])));
                }
                cur--;
            }
            if(s.empty())continue;
            auto it = s.end();
            it--;
            while((*it).first>=j.second-1){
                if((*it).second-1<=la){
                    all++;
                }
                if(it==s.begin())break;
                it--;
            }
        }
    }
    return all;
}

// signed main(){
//     cout<<count_rectangles({{4, 8, 7, 5, 6},
// {7, 4, 10, 3, 5},
// {9, 7, 20, 14, 2},
// {9, 14, 7, 3, 6},
// {5, 7, 5, 2, 7},
// {4, 5, 13, 5, 6}});
// }

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:73:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int j = 0;j<rngr[i].size();j++){
      |                       ~^~~~~~~~~~~~~~~
rect.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             if(it<rngr[i+1].size()&&rngr[i+1][it]==rngr[i][j]){
      |                ~~^~~~~~~~~~~~~~~~~
rect.cpp:94:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             while(col[j]<rngc[j].size()&&rngc[j][col[j]].first<i){
      |                   ~~~~~~^~~~~~~~~~~~~~~
rect.cpp:102:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |             for(int e = 0;e<lol[j].size();e++){
      |                           ~^~~~~~~~~~~~~~
rect.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |                     if(it<lol[st].size()&&lol[st][it].first==lol[j][e].first){
      |                        ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28