Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ///Usor (bine mediu..)
- #include <fstream>
- #include <algorithm>
- using namespace std;
- ifstream cin("dreptunghi1.in");
- ofstream cout("dreptunghi1.out");
- const int mxN = 1e4;
- pair<int,int> p[mxN+2];
- int st[mxN+1],l[mxN+1],r[mxN+1],v[mxN+1];
- int skyline(int v[], int n)
- {
- int top = 0, sol = 0;
- for(int i = 1;i<=n;i++)
- l[i] = r[i] = 0;
- for(int i = 1;i<=n;i++)
- {
- while(top > 0 && v[st[top]] > v[i])
- r[st[top]] = i , top--;
- st[++top] = i;
- }
- while(top>0) r[st[top]] = n+1, top--;
- for(int i = n;i>0;i--)
- {
- while(top > 0 && v[st[top]] > v[i])
- l[st[top]] = i, top--;
- st[++top] = i;
- }
- for(int i = 1;i<=n;i++)
- {
- int res = v[i] * (r[i] - l[i] - 1);
- sol = max(sol,res);
- }
- return sol;
- }
- int main()
- {
- int n , m , z;
- cin>>n>>m>>z;
- for(int i = 1;i<=z;i++)
- cin>>p[i].first>>p[i].second;
- sort(p+1,p+1+z);
- p[z+1].first = p[z+1].second = 1e9;
- int k = 1, sol = 0;
- for(int i = 1;i<=n;i++)
- {
- for(int j = 1;j<=m;j++)
- {
- if(i >= p[k].first)
- {
- while(i>p[k].first) k++;
- while(j > p[k].second && p[k].first <= i) k++;
- }
- if(i==p[k].first&&j==p[k].second) v[j] = 0;
- else v[j]++;
- }
- sol = max(sol,skyline(v,m));
- }
- cout<<sol<<'\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement