Cod sursa(job #2521199)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 10 ianuarie 2020 15:37:28
Problema Light2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>

#define NMAX 10005
using namespace std;

ifstream fin("dreptunghi1.in");
ofstream fout("dreptunghi1.out");

map<pair<int, int>, bool> mp;
vector<int> h[NMAX];
int st[NMAX + 5][2], v[NMAX], poz[NMAX], last[NMAX], pz;
long long arieM;

int main()
{
    int n, m, z;
    fin >> n >> m >> z;

    for(int i = 1; i <= z; ++i)
    {
        int x, y;
        fin >> x >> y;

        if(mp.find(make_pair(x, y)) == mp.end())
        {
            h[x].push_back(y);
            mp[make_pair(x, y)] = 1;
        }
    }

    for(int j = 1; j <= m; ++j)
        last[j] = 0;

    st[pz][0] = -1;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j < h[i].size(); ++j)
            last[h[i][j]] = i;

        last[m + 1] = i;
        for(int j = 1; j <= m + 1; ++j)
        {
            v[j] = i - last[j];
            if(v[j] > st[pz][0])
                st[++pz][0] = v[j], st[pz][1] = j;
            else
            {
                while(st[pz][0] >= v[j])
                {
                    arieM = max(arieM, 1LL * (j - st[pz - 1][1] - 1) * st[pz][0]);
                    --pz;
                }
                st[++pz][0] = v[j], st[pz][1] = j;
            }
        }
        --pz;
    }

    fout << arieM << '\n';
    return 0;
}