Submission #678285

#	Time	Username	Problem	Language	Result	Execution time	Memory
678285		someone	Rectangles (IOI19_rect)	C++14	100 / 100	3142 ms	841612 KiB

rect

#include <bits/stdc++.h>
using namespace std;
 
struct Req {
    bool isUpd;
    int x, y;
};
 
const int N = 2500 + 42, M = 1 << 12;
 
vector<int> val;
vector<pair<int, int>> fin[N][N][2];
int n, m, pre[N][N], nb[N][N], sum[2*M];

inline int add(int l, int r, int i) {
    if(pre[l][r] != i+1)
        nb[l][r] = 0;
    pre[l][r] = i;
    return ++nb[l][r];
}

void upd(int i, int v) {
    i += M;
    while(i) {
        sum[i] += v;
        i >>= 1;
    }
}

int getVal(int i) {
    i += M;
    int ans = sum[i];
    while(i) {
        if(i & 1)
            ans += sum[i-1];
        i >>= 1;
    }
    return ans;
}
 
long long count_rectangles(vector<vector<int>> a) {
    n = (int)a.size();
    m = (int)a[0].size();
 
    for(int i = n-2; i > 0; 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)
                fin[i][maxi.back()+1][0].push_back({j-1, add(maxi.back()+1, j-1, i)-1});
            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())
                fin[i][j+1][0].push_back({maxi.back()-1, add(j+1, maxi.back()-1, i)-1});
            maxi.push_back(j);
        }
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            nb[i][j] = pre[i][j] = 0;
    for(int j = m-2; j > 0; 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() && a[maxi.back()][j] != a[i][j] && maxi.back() < i-1)
                fin[maxi.back()+1][j][1].push_back({i-1, add(maxi.back()+1, i-1, j)-1});
            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())
                fin[i+1][j][1].push_back({maxi.back()-1, add(i+1, maxi.back()-1, j)-1});
            maxi.push_back(i);
        }
    }
    
    int ans = 0;
    for(int i = 1; i < n-1; i++) {
        for(int j = 1; j < m-1; j++) {
            vector<Req> req;
            for(auto pii : fin[i][j][0])
                req.push_back({true, pii.first - j, pii.second});
            for(auto pii : fin[i][j][1])
                req.push_back({false, pii.second, pii.first - i});
            sort(req.begin(), req.end(),
            [](Req a, Req b) {
                if(a.y == b.y)
                    return a.isUpd && !b.isUpd;
                return a.y > b.y;
            });
            for(Req q : req) {
                if(q.isUpd)
                    upd(q.x, 1);
                else
                    ans += getVal(q.x);
            }
            for(Req q : req)
                if(q.isUpd)
                    upd(q.x, -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