Submission #925557

#	Time	Username	Problem	Language	Result	Execution time	Memory
925557		hmm789	Rectangles (IOI19_rect)	C++14	72 / 100	2422 ms	1048576 KiB

rect

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define INF 1000000000000000000
#define MOD 998244353

int fw[2505];

void update(int x, int v) {
    for(x++; x < 2505; x += x&-x) fw[x] += v;
}

void update(int x, int y, int v) {
    update(x, v); update(y+1, -v);
}

int query(int x) {
    int ans = 0;
    for(x++; x; x -= x&-x) ans += fw[x];
    return ans;
}

long long count_rectangles(vector<vector<int>> a) {
    int m = a.size(), n = a[0].size();
    vector<int> toth[n][n], totv[m][m];
    vector<pair<int, int>> goodh[m][n], goodv[m][n];
    for(int i = 1; i < m-1; i++) {
        stack<int> s;
        int l[n], r[n];
        for(int j = 0; j < n; j++) {
            while(s.size() && a[i][s.top()] <= a[i][j]) s.pop();
            if(s.size()) l[j] = s.top();
            else l[j] = -1;
            s.push(j);
        }
        while(s.size()) s.pop();
        for(int j = n-1; j >= 0; j--) {
            while(s.size() && a[i][s.top()] <= a[i][j]) s.pop();
            if(s.size()) r[j] = s.top();
            else r[j] = -1;
            s.push(j);
        }
        for(int j = 0; j < n; j++) if(l[j] != -1 && r[j] != -1) toth[l[j]][r[j]].push_back(i);
    }
    for(int i = 0; i < n; i++) {
        for(int j = i+2; j < n; j++) {
            if(!toth[i][j].size()) continue;
            int prv = -1;
            toth[i][j].erase(unique(toth[i][j].begin(), toth[i][j].end()), toth[i][j].end());
            for(int k = 1; k < toth[i][j].size(); k++) {
                if(toth[i][j][k]-toth[i][j][k-1] > 1) {
                    while(prv < k-1) {
                        goodh[toth[i][j][prv+1]][i+1].push_back({toth[i][j][k-1], j-1});
                        prv++;
                    }
                }
            }
            while(prv < (int)toth[i][j].size()-1) {
                goodh[toth[i][j][prv+1]][i+1].push_back({toth[i][j][toth[i][j].size()-1], j-1});
                prv++;
            }
        }
    }
    for(int i = 1; i < n-1; i++) {
        stack<int> s;
        int l[m], r[m];
        for(int j = 0; j < m; j++) {
            while(s.size() && a[s.top()][i] <= a[j][i]) s.pop();
            if(s.size()) l[j] = s.top();
            else l[j] = -1;
            s.push(j);
        }
        while(s.size()) s.pop();
        for(int j = m-1; j >= 0; j--) {
            while(s.size() && a[s.top()][i] <= a[j][i]) s.pop();
            if(s.size()) r[j] = s.top();
            else r[j] = -1;
            s.push(j);
        }
        for(int j = 0; j < m; j++) if(l[j] != -1 && r[j] != -1) totv[l[j]][r[j]].push_back(i);
    }
    for(int i = 0; i < m; i++) {
        for(int j = i+2; j < m; j++) {
            if(!totv[i][j].size()) continue;
            int prv = -1;
            totv[i][j].erase(unique(totv[i][j].begin(), totv[i][j].end()), totv[i][j].end());
            for(int k = 1; k < totv[i][j].size(); k++) {
                if(totv[i][j][k]-totv[i][j][k-1] > 1) {
                    while(prv < k-1) {
                        goodv[i+1][totv[i][j][prv+1]].push_back({j-1, totv[i][j][k-1]});
                        prv++;
                    }
                }
            }
            while(prv < (int)totv[i][j].size()-1) {
                goodv[i+1][totv[i][j][prv+1]].push_back({j-1, totv[i][j][totv[i][j].size()-1]});
                prv++;
            }
        }
    }
    long long ans = 0;
    for(int i = 1; i < m-1; i++) {
        for(int j = 1; j < n-1; j++) {
            sort(goodh[i][j].begin(), goodh[i][j].end());
            sort(goodv[i][j].begin(), goodv[i][j].end());
            int idx = 0;
            for(auto k : goodh[i][j]) {
                while(idx < goodv[i][j].size() && goodv[i][j][idx].first <= k.first) {
                    update(j, goodv[i][j][idx++].second, 1);
                }
                ans += query(k.second);
            }
            for(int k = 0; k < idx; k++) update(j, goodv[i][j][k].second, -1);
        }
    }
    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:50:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for(int k = 1; k < toth[i][j].size(); k++) {
      |                            ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:87:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             for(int k = 1; k < totv[i][j].size(); k++) {
      |                            ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 while(idx < goodv[i][j].size() && goodv[i][j][idx].first <= k.first) {
      |                       ~~~~^~~~~~~~~~~~~~~~~~~~

• 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