Submission #601311

#	Time	Username	Problem	Language	Result	Execution time	Memory
601311		MohamedFaresNebili	Rectangles (IOI19_rect)	C++14	100 / 100	3203 ms	735304 KiB

rect

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#pragma GCC optimize("unroll-loops")
 
            using namespace std;
 
            using ll = long long;
            using ii = pair<ll, ll>;
            using vi = vector<int>;
 
            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
 
            const int oo = 1000 * 1000 * 1000 + 7;
 
            vector<pair<int, int>> R[2505][2505], D[2505][2505];
 
            ll count_rectangles(vector<vector<int>> A) {
                int N = A.size(), M = A[0].size(); int res = 0;
                for(int l = 0; l < N; l++) {
                    vector<int> S;
                    for(int i = 0; i < M; i++) {
                        bool flag = 1;
                        while(!S.empty() && A[l][i] >= A[l][S.back()]) {
                            if(A[l][i] == A[l][S.back()]) flag = 0;
                            if(i - S.back() > 1)
                                R[l][S.back() + 1].push_back({i - 1, l});
                            S.pop_back();
                        }
                        if(flag && !S.empty() && i - S.back() > 1)
                            R[l][S.back() + 1].push_back({i - 1, l});
                        S.push_back(i);
                    }
                }
 
                for(int l = 0; l < M; l++) {
                    vector<int> S;
                    for(int i = 0; i < N; i++) {
                        bool flag = 1;
                        while(!S.empty() && A[i][l] >= A[S.back()][l]) {
                            if(A[i][l] == A[S.back()][l]) flag = 0;
                            if(i - S.back() > 1)
                                D[S.back() + 1][l].push_back({i - 1, l});
                            S.pop_back();
                        }
                        if(flag && !S.empty() && i - S.back() > 1)
                            D[S.back() + 1][l].push_back({i - 1, l});
                        S.push_back(i);
                    }
                }
 
                for(int l = N - 1; l >= 0; l--) {
                    for(int i = M - 1; i >= 0; i--) {
                        sort(R[l][i].begin(), R[l][i].end());
                        sort(D[l][i].begin(), D[l][i].end());
 
                        for(int j = 0; j < R[l][i].size(); j++) {
                            int k = lb(R[l + 1][i].begin(), R[l + 1][i].end(), R[l][i][j]) - R[l + 1][i].begin();
                            if(k == R[l + 1][i].size() || R[l + 1][i][k].ff != R[l][i][j].ff) continue;
                            R[l][i][j] = R[l + 1][i][k];
                        }
 
                        for(int j = 0; j < D[l][i].size(); j++) {
                            int k = lb(D[l][i + 1].begin(), D[l][i + 1].end(), D[l][i][j]) - D[l][i + 1].begin();
                            if(k == D[l][i + 1].size() || D[l][i + 1][k].ff != D[l][i][j].ff) continue;
                            D[l][i][j] = D[l][i + 1][k];
                        }
                    }
                }
 
                for(int l = 1; l < N - 1; l++) {
                    for(int i = 1; i < M - 1; i++) {
                        for(auto u : R[l][i])
                            for(auto v : D[l][i])
                                if(u.ff <= v.ss && v.ff <= u.ss)
                                    res++;
                    }
                }
                return res;
            }

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:61:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                         for(int j = 0; j < R[l][i].size(); j++) {
      |                                        ~~^~~~~~~~~~~~~~~~
rect.cpp:63:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                             if(k == R[l + 1][i].size() || R[l + 1][i][k].ff != R[l][i][j].ff) continue;
      |                                ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:67:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |                         for(int j = 0; j < D[l][i].size(); j++) {
      |                                        ~~^~~~~~~~~~~~~~~~
rect.cpp:69:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                             if(k == D[l][i + 1].size() || D[l][i + 1][k].ff != D[l][i][j].ff) continue;
      |                                ~~^~~~~~~~~~~~~~~~~~~~~

• 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: 28 / 28