Submission #780919

#	Time	Username	Problem	Language	Result	Execution time	Memory
780919		1bin	Rectangles (IOI19_rect)	C++14	100 / 100	1014 ms	187084 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3005;
ll n, m, ans;
stack<int> st[NMAX];
pair<int, int> p[NMAX][NMAX];

ll count_rectangles(vector<vector<int>> a) {
    n = a.size(); m = a[0].size();
    for(int i = 0; i < m; i++){
        st[i].emplace(0);
        for(int j = 0; j < m; j++) p[i][j] = {-2, -2};
    }

    for(int i = 0; i + 1 < n; i++){
        stack<pair<int, vector<int>>> s;

        for(int j = 0; j < m; j++){
            vector<int> cur;
            int init = 0;
            auto merge = [&](vector<int> & v){
                if(!init) init = 1, cur = v;
                else{
                    vector<int> tmp;
                    int j = 0;
                    for(int i = 0; i < cur.size(); i++){
                        while(j < v.size() && v[j] < cur[i]) j++;
                        if(j < v.size() && v[j] == cur[i]) tmp.emplace_back(cur[i]);
                    }
                    swap(cur, tmp);
                }
            };

            while(s.size() && a[i][s.top().first] <= a[i][j]){
                auto[x, v] = s.top(); s.pop();
                merge(v);
                if(s.size() && a[i][x] < a[i][j]){
                    int l = s.top().first;
                    if(p[l + 1][j - 1].second != i - 1) p[l + 1][j - 1].first = i;
                    p[l + 1][j - 1].second = i;
                    int up = p[l + 1][j - 1].first;
                    ans += cur.end() - lower_bound(all(cur), up);
                }
            }
            vector<int> v;
            while(st[j].size() && a[st[j].top()][j] <= a[i + 1][j]){
                int y = st[j].top(); st[j].pop();
                if(st[j].size() && a[y][j] < a[i + 1][j]) v.emplace_back(st[j].top() + 1);
            }
            st[j].emplace(i + 1);
            reverse(all(v));
            merge(v);
            s.emplace(j, cur);
        }
    } 
	return ans;
}

/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n, vector<int>(m));
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> v[i][j];
    cout << count_rectangles(v);
    return 0;
} 
*/

Compilation message (stderr)

rect.cpp: In lambda function:
rect.cpp:30:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                     for(int i = 0; i < cur.size(); i++){
      |                                    ~~^~~~~~~~~~~~
rect.cpp:31:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                         while(j < v.size() && v[j] < cur[i]) j++;
      |                               ~~^~~~~~~~~~
rect.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |                         if(j < v.size() && v[j] == cur[i]) tmp.emplace_back(cur[i]);
      |                            ~~^~~~~~~~~~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:39:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |                 auto[x, v] = s.top(); s.pop();
      |                     ^

• 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