Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

苯质上是个H2O题,贪心,能切就切,一堆STL都0ms

Posted by KatrineYang at 2016-09-02 11:42:12 on Problem 1255
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;

int xIdx[40004], yIdx[40004];
int xfen[200], yfen[200];


struct intv{
	int start, end;
	intv(int s, int e): start(s), end(e){}
};

ostream& operator<<(ostream& o, const intv& i){
	o << '[' << i.start << "," << i.end << ']';
	return o;
}

vector<intv> xIntvs[200], yIntvs[200];

int maxArea(int x1, int y1, int x2, int y2){
	int minxIdx = xIdx[x1] + 1, maxxIdx = xIdx[x2] - 1;
	for(int i = minxIdx; i <= maxxIdx; i++){
		int sz = xIntvs[i].size();
		for(int j = 0; j < sz; j++){
			if(xIntvs[i][j].start <= y1 && xIntvs[i][j].end >= y2){
				int mx1 = maxArea(x1, y1, xfen[i], y2);
				int mx2 = maxArea(xfen[i], y1, x2, y2);
				return (mx1 > mx2) ? mx1 : mx2;
			}
		}
	}
	int minyIdx = yIdx[y1] + 1, maxyIdx = yIdx[y2] - 1;
	for(int i = minyIdx; i <= maxyIdx; i++){
		int sz = yIntvs[i].size();
		for(int j = 0; j < sz; j++){
			if(yIntvs[i][j].start <= x1 && yIntvs[i][j].end >= x2){
				int mx1 = maxArea(x1, y1, x2, yfen[i]);
				int mx2 = maxArea(x1, yfen[i], x2, y2);
				return (mx1 > mx2) ? mx1 : mx2;
			}
		}
	}
	return (x2-x1) * (y2-y1);
}

bool compare(const intv &i1, const intv &i2){
	return i1.start < i2.start || (i1.start == i2.start && i1.end < i2.end);
}

int main() {
	int T;
	scanf("%d", &T);
	for(int ii = 0; ii < T; ii++){
		int mnX = 2147483647, mnY = 2147483647;
		int x, y;
		scanf("%d%d", &x, &y);
		int xl[110], yl[110], xh[110], yh[110];
		int gs;
		scanf("%d", &gs);
		for(int i = 0; i < gs; i++){
			scanf("%d%d%d%d", &xl[i], &yl[i], &xh[i], &yh[i]);
			if(xl[i] < mnX) mnX = xl[i];
			if(yl[i] < mnY) mnY = yl[i];
		}
		for(int i = 0; i < gs; i++){
			xl[i] -= mnX, yl[i] -= mnY, xh[i] -= mnX, yh[i] -= mnY;
		}
		int mxX = x, mxY = y;
		bool xUsed[40004] = {0}, yUsed[40004] = {0};

		int xgs = 0, ygs = 0;
		for(int i = 0; i < gs; i++){
			if(xl[i] != 0 && xUsed[xl[i]]==0){
				xUsed[xl[i]] = 1;
				xfen[xgs] = xl[i];
				//xIdx[xl[i]] = xgs;
				xgs++;
			}
			if(xh[i] != mxX && xUsed[xh[i]] == 0){
				xUsed[xh[i]] = 1;
				xfen[xgs] = xh[i];
				//xIdx[xh[i]] = xgs;
				xgs++;
			}
			if(yl[i] != 0 && yUsed[yl[i]] == 0){
				yUsed[yl[i]] = 1;
				yfen[ygs] = yl[i];
				//yIdx[yl[i]] = ygs;
				ygs++;
			}
			if(yh[i] != mxY && yUsed[yh[i]]==0){
				yUsed[yh[i]] = 1;
				yfen[ygs] = yh[i];
				//yIdx[yh[i]] = ygs;
				ygs++;
			}
		}
		sort(xfen, xfen+xgs);
		sort(yfen, yfen+ygs);
		for(int i = 0; i < xgs; i++) xIdx[xfen[i]] = i;
		for(int j = 0; j < ygs; j++) yIdx[yfen[j]] = j;
		xIdx[0] = yIdx[0] = -1;
		xIdx[mxX] = xgs, yIdx[mxY] = ygs;
		vector<intv> xintvs[200], yintvs[200];
		for(int i = 0; i < gs; i++){
			int x1 = xl[i], x2 = xh[i], y1 = yl[i], y2 = yh[i];
			if(x1 != 0){
				xintvs[xIdx[x1]].push_back(intv(y1, y2));
			}
			if(x2 != mxX){
				xintvs[xIdx[x2]].push_back(intv(y1, y2));
			}
			if(y1 != 0){
				yintvs[yIdx[y1]].push_back(intv(x1, x2));
			}
			if(y2 != mxY){
				yintvs[yIdx[y2]].push_back(intv(x1, x2));
			}
		}
		for(int i = 0; i < xgs; i++) sort(xintvs[i].begin(), xintvs[i].end(), compare);
		for(int j = 0; j < ygs; j++) sort(yintvs[j].begin(), yintvs[j].end(), compare);

		for(int i = 0; i < xgs; i++) xIntvs[i].clear();
		for(int j = 0; j < ygs; j++) yIntvs[j].clear();
		for(int i = 0; i < xgs; i++){
			//vector<intv> &temp = xintvs[i];
			int sz = xintvs[i].size();
			int ks = xintvs[i][0].start;
			int js = xintvs[i][0].end;
			for(int j = 0; j < sz; j++){
				if(j == sz-1 || xintvs[i][j+1].start > js){
					xIntvs[i].push_back(intv(ks, js));
					if(j != sz-1){
						ks = xintvs[i][j+1].start;
						js = xintvs[i][j+1].end;
					}
				}
				else{
					if(xintvs[i][j+1].end > js) js = xintvs[i][j+1].end;
				}
			}
		}
		for(int i = 0; i < ygs; i++){
			//vector<intv> &temp = yintvs[i];
			int sz = yintvs[i].size();
			int ks = yintvs[i][0].start;
			int js = yintvs[i][0].end;
			for(int j = 0; j < sz; j++){
				if(j == sz-1 || yintvs[i][j+1].start > js){
					yIntvs[i].push_back(intv(ks,js));
					if(j != sz-1){
						ks = yintvs[i][j+1].start;
						js = yintvs[i][j+1].end;
					}
				}
				else{
					if(yintvs[i][j+1].end > js) js = yintvs[i][j+1].end;
				}
			}
		}

		int mA = maxArea(0, 0, mxX, mxY);
		printf("%d\n", mA);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator