AC代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef int ty;
typedef pair<ty,ty> pa;
const ty L = 30010,W = 30010,N = 5010;
ty n,l,w;
pa a[N];
ty ind = 1;
ty h[W],lef[W],rig[W];
ty ans = 0;
int main(){
    cin >> w >> l >> n;
    rig[w] = w;
    for(ty i = 1;i <= n;i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a + 1,a + 1 + n,[](pa a,pa b){return a.second > b.second;});
    for(ty i = l - 1;i >= 0;i--){
        while(ind <= n && a[ind].second == i + 1){
            h[a[ind].first] = 0;
            ind++;
        }
        for(ty j = 0;j <= w;j++){
            h[j]++;
            //cout << h[j] << " ";
        }
        //cout << "\n";
        for(ty j = 1;j <= w;j++){
            lef[j] = j - 1;
            while(lef[j] && h[lef[j]] >= h[j]){
                lef[j] = lef[lef[j]];
            }
        }
        for(ty j = w - 1;j >= 0;j--){
            rig[j] = j + 1;
            while(rig[j] != w && h[rig[j]] >= h[j]){
                rig[j] = rig[rig[j]];
            }
        }
        for(ty j = 0;j <= w;j++){
            ans = max(ans,h[j] * (rig[j] - lef[j]));
        }
    }
    cout << ans;
    system("pause");
    return 0;
}

hack数据： in: 1 2 2 0 1 1 1 out: 2