Submission #580426

#	Time	Username	Problem	Language	Result	Execution time	Memory
580426		SlavicG	Rectangles (IOI19_rect)	C++17	100 / 100	3170 ms	781056 KiB

rect

#include "rect.h"
#include "bits/stdc++.h"

#define pb push_back
#define all(a) a.begin(),a.end()
using namespace std;
using ll = long long;

struct event {
    int time, val, type;
};

bool cmp(event a, event b) {
    if(a.time > b.time) return 1;
    if(a.time < b.time) return 0;
    return a.type < b.type;
}

const int N = 3000;
ll fen[N];
void modif(int u, int val) {
    for(int i = u + 1; i < N; i += i & -i) fen[i] += val;
}
ll query(int u) {
    ll ret = 0;
    for(int i = u + 1; i > 0; i -= i & -i) ret += fen[i];
    return ret;
}
long long count_rectangles(std::vector<std::vector<int>> a) {
    int n = a.size(), m = a[0].size();
    vector<pair<int, int>> right[n + 1][m + 1], down[n + 1][m + 1];
    for(int i = 0; i < n; ++i) {
        stack<int> s;
        for(int j = m - 1; j >= 0; --j) {
            while(!s.empty() && a[i][j] > a[i][s.top()]) {
                if(j + 1 <= s.top() - 1) {
                    right[i][j + 1].pb(make_pair(s.top() - 1 - j, 1));
                }
                s.pop();
            }
            if(!s.empty()) {
                if(j + 1 <= s.top() - 1) {
                    right[i][j + 1].pb(make_pair(s.top() - 1 - j, 1));
                }
                if(a[i][s.top()] == a[i][j]) s.pop();
            }
            s.push(j);
        }
    }

    for(int i = 0; i < m; ++i) {
        stack<int> s;
        for(int j = n - 1; j >= 0; --j) {
            while(!s.empty() && a[j][i] > a[s.top()][i]) {
                if(j + 1 <= s.top() - 1) {
                    down[j + 1][i].pb(make_pair(s.top() - 1 - j, 1));
                }
                s.pop();
            }

            if(!s.empty()) {
                if(j + 1 <= s.top() - 1) {
                    down[j + 1][i].pb(make_pair(s.top() - 1 - j, 1));
                }
                if(a[s.top()][i] == a[j][i]) s.pop();
            }
            s.push(j);
        }
    }

    for(int i = n - 1; i >= 0; --i) {
        for(int j = m - 1; j >=0; --j) {
            for(auto& p: right[i][j]) {
                auto it = lower_bound(all(right[i + 1][j]), p);
                if(it != right[i + 1][j].end() && it->first == p.first) {
                    p.second = it->second + 1;
                }
            }
            for(auto& p: down[i][j]) {
                auto it = lower_bound(all(down[i][j + 1]), p);
                if(it != down[i][j + 1].end() && it->first == p.first) {
                    p.second = it->second + 1;
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 1; i < n - 1; ++i) {
        for(int j = 1; j < m - 1; ++j) {
            vector<event> v;
            for(auto& p: down[i][j]) {
                v.pb({p.second, p.first, 1});
            }
            for(auto& p: right[i][j]) {
                v.pb({p.first, p.second, 2});
            }
            sort(all(v), cmp);
            for(auto x: v) {
                if(x.type == 1) {
                    modif(x.val, 1);
                } else {
                    ans += query(x.val);
                }
            }
            for(auto x: v) if(x.type == 1) modif(x.val, -1);
        }
    }
    return ans;
}

• 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