Submission #657857

#	Time	Username	Problem	Language	Result	Execution time	Memory
657857		someone	Rectangles (IOI19_rect)	C++14	72 / 100	5056 ms	379128 KiB

rect

#include <bits/stdc++.h>
//#define int long long
using namespace std;
 
struct Req {
    int deb, fin, coeff, id;
};
 
const int N = 2500 + 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]) {
                    if(d >= j-nb[maxi.back()][i]) {
                        int reqId = val.size();
                        val.push_back(-(i-maxi.back()-1));
                        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]) {
                    if(d >= j-nb[i][maxi.back()]) {
                        int reqId = val.size();
                        val.push_back(-(maxi.back()-i-1));
                        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]++;
    }
    long long 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