Submission #579572

#	Time	Username	Problem	Language	Result	Execution time	Memory
579572		2fat2code	Rectangles (IOI19_rect)	C++17	31 / 100	1018 ms	441992 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
#define int long long
using namespace std;

const int nmax = 2505;

int n, m;
vector<vector<int>>a;
long long aib[nmax], ans;
vector<pair<int,int>>LE[nmax][nmax], UP[nmax][nmax];

void update(int pos, long long val){
    for(int i=pos;i<nmax;i+=i&-i){
        aib[i] += val;
    }
}

long long query(int pos){
    long long rs = 0;
    for(int i=pos;i>=1;i-=i&-i){
        rs += aib[i];
    }
    return rs;
}

struct event{
    int latime, inaltime, tip;
    friend bool operator < (event A, event B){
        if(A.latime != B.latime){
            return A.latime < B.latime;
        }
        else{
            return A.tip < B.tip;
        }
    }
};

vector<event> O_o;

long long count_rectangles(vector<vector<int32_t>> a) {
	n = a.size();
	m = a[0].size();
    for(int i=0;i<m;i++){
        vector<pair<int,int>> st;
        for(int j=0;j<n;j++){
            for(int t=((int)st.size())-2;t>=0;t--){
                if(st[t].fr > st[t+1].fr && a[j][i] > st[t+1].fr){
                    UP[j - 1][i].push_back({st[t].sc + 1, 1});
                    st.pop_back();
                }
                else if(st[t+1].fr >= a[j][i]){
                    break;
                }
            }
            if(j >= 1)reverse(all(UP[j - 1][i]));
            st.push_back({a[j][i], j});
        }
    }
    for(int i=0;i<n;i++){
        vector <pair<int,int>> st;
        for(int j=0;j<m;j++){
            for(int t=st.size()-2;t>=0;t--){
                if(st[t].fr > st[t+1].fr && a[i][j] > st[t+1].fr){
                    LE[i][j - 1].push_back({st[t].sc + 1, 1});
                    st.pop_back();
                }
                else if(st[t+1].fr >= a[i][j]){
                    break;
                }
            }
            if(j >= 1)reverse(all(LE[i][j - 1]));
            st.push_back({a[i][j], j});
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i > 0){
                for(auto &it : LE[i][j]){
                    auto it1 = lower_bound(all(LE[i-1][j]), it) - LE[i-1][j].begin();
                    if(it1 < LE[i-1][j].size() && LE[i-1][j][it1].fr == it.fr){
                        it.sc = LE[i-1][j][it1].sc + 1;
                    }
                }
            }
            if(j > 0){
                for(auto &it : UP[i][j]){
                    auto it1 = lower_bound(all(UP[i][j-1]), it) - UP[i][j-1].begin();
                    if(it1 < UP[i][j-1].size() && UP[i][j-1][it1].fr == it.fr){
                        it.sc = UP[i][j-1][it1].sc + 1;
                    }
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            O_o.clear();
            for(auto it : LE[i][j]){
                O_o.push_back({j - it.fr + 1, it.sc, 1});
            }
            for(auto it : UP[i][j]){
                O_o.push_back({it.sc, i - it.fr + 1, 2});
            }
            sort(all(O_o));
            for(auto it : O_o){
                if(it.tip == 1){
                    update(nmax - it.inaltime, 1);
                }
                else{
                    ans += query(nmax - it.inaltime);
                }
            }
            for(auto it : O_o){
                if(it.tip == 1){
                    update(nmax - it.inaltime, -1);
                }
            }
        }
    }
	return ans;
}


/**
6 5
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:84:28: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                     if(it1 < LE[i-1][j].size() && LE[i-1][j][it1].fr == it.fr){
      |                        ~~~~^~~~~~~~~~~~~~~~~~~
rect.cpp:92:28: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                     if(it1 < UP[i][j-1].size() && UP[i][j-1][it1].fr == it.fr){
      |                        ~~~~^~~~~~~~~~~~~~~~~~~

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