Submission #595379

#	Time	Username	Problem	Language	Result	Execution time	Memory
595379		someone	Rectangles (IOI19_rect)	C++14	72 / 100	5095 ms	482204 KiB

rect

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

struct Req {
    int deb, fin, coeff, id;
};

const int N = 3e3 + 42;

vector<Req> req[N];
vector<int> deb[N][N], val;
int n, m, pre[N][N], nb[N][N];

long long count_rectangles(vector<vector<int>> a) {
    n = a.size();
    m = a[0].size();

    for(int i = 1; i < n-1; i++) {
        vector<int> maxi;
        for(int j = 0; j < m; j++) {
            while(!maxi.empty() && a[i][maxi.back()] < a[i][j])
                maxi.pop_back();
            if(!maxi.empty() && a[i][maxi.back()] != a[i][j] && maxi.back() < j-1)
                deb[i][j].push_back(maxi.back());
            maxi.push_back(j);
        }
        maxi.clear();
        for(int j = m-1; j > -1; j--) {
            while(!maxi.empty() && a[i][maxi.back()] < a[i][j])
                maxi.pop_back();
            if(!maxi.empty() && j+1 < maxi.back())
                deb[i][maxi.back()].push_back(j);
            maxi.push_back(j);
        }
    }

    for(int j = 1; j < m-1; j++) {
        vector<int> maxi;
        for(int i = 0; i < n; i++) {
            while(!maxi.empty() && a[maxi.back()][j] < a[i][j])
                maxi.pop_back();
            if(!maxi.empty() && maxi.back() < i-1) {
                if(pre[maxi.back()][i] != j-1)
                    nb[maxi.back()][i] = 0;
                nb[maxi.back()][i]++;
                pre[maxi.back()][i] = j;
                for(int d : deb[maxi.back()+1][j+1]) {
                    //cout << d << ' ' << j - nb[maxi.back()][i] << ' ' << j << ' ' << nb[maxi.back()][i] << ' ' << maxi.back() << ' ' << i << '\n';
                    if(d >= j-nb[maxi.back()][i]) {
                        int reqId = val.size();
                        val.push_back(-(i-maxi.back()-1));
                        //cout << d << ' ' << j+1 << ' ' << maxi.back()+1 << ' ' << i << ' ' << i-maxi.back()-1 << '\n';
                        req[maxi.back()+1].push_back({d, j+1, -1, reqId});
                        req[i].push_back({d, j+1, 1, reqId});
                    }
                }
            }
            maxi.push_back(i);
        }
        maxi.clear();
        for(int i = n-1; i > -1; i--) {
            while(!maxi.empty() && a[maxi.back()][j] < a[i][j])
                maxi.pop_back();
            if(!maxi.empty() && i+1 < maxi.back() && a[maxi.back()][j] != a[i][j]) {
                if(pre[i][maxi.back()] != j-1)
                    nb[i][maxi.back()] = 0;
                nb[i][maxi.back()]++;
                pre[i][maxi.back()] = j;
                for(int d : deb[i+1][j+1]) {
                    //cout << d << ' ' << j - nb[i][maxi.back()] << ' ' << j << ' ' << nb[i][maxi.back()] << i <<  ' ' << maxi.back() << '\n';
                    if(d >= j-nb[i][maxi.back()]) {
                        int reqId = val.size();
                        val.push_back(-(maxi.back()-i-1));
                        //cout << d << ' ' << j+1 << ' ' << i+1 << ' ' << maxi.back() << ' ' << maxi.back()-i-1 << '\n';
                        req[i+1].push_back({d, j+1, -1, reqId});
                        req[maxi.back()].push_back({d, j+1, 1, reqId});
                    }
                }
            }
            maxi.push_back(i);
        }
    }

    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            nb[i][j] = 0;

    for(int i = 1; i < n; i++) {
        for(Req r : req[i])
            val[r.id] += nb[r.deb][r.fin] * r.coeff;
        for(int j = 0; j < m; j++)
            for(int d : deb[i][j])
                nb[d][j]++;
    }
    int ans = 0;
    for(int i : val)
        if(i == 0)
            ans++;
    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: 0 / 28