第一題:染色問題(NOIP 2009模擬試験問題)


せんしょくもんだい
問題の説明:
0から10000000までの数軸があり、最初の色は白です.今ではその中の1段を黒や白に染め続け、全部でN段(1<=N<=5000)に染めている人がいます.あなたの任務はプログラムを作成して、最後に最も長い白いセグメントを見つけることです.
入力:最初の行は1つの数Nしかありません.次のN行は、ai bi ciというフォーマットで、1つのセグメントを染めるたびに情報です.
ai、biは整数、ciは記号「b」または「w」の3つをスペースで区切って、今回aiからbiに染められたことを示し、使用色はci('w’は白、'b’は黒)で、0出力:2つの数x,y(x<=y)のみで、最も長い白いセグメントをスペースで区切ります.複数の解があればXの最小の解を出力する.
入出力サンプル
dye.in
dye.out
4 1 999999997 b 40 300 w 300 634 w 43 47 b  
48 634  
/******************************************************************************************************
 ** Copyright (C) 2011.07.01-2013.07.01
 ** Author: famousDT <[email protected]>
 ** Edit date: 2011-10-17
******************************************************************************************************/
#include <stdio.h>
#include <stdlib.h>//abs,atof(string to float),atoi,atol,atoll
#include <math.h>//atan,acos,asin,atan2(a,b)(a/b atan),ceil,floor,cos,exp(x)(e^x),fabs,log(for E),log10
#include <vector>
#include <queue>
#include <map>
#include <time.h>
#include <set>
#include <list>
#include <stack>
#include <string>
#include <iostream>
#include <assert.h>
#include <string.h>//memcpy(to,from,count
#include <ctype.h>//character process:isalpha,isdigit,islower,tolower,isblank,iscntrl,isprll
#include <algorithm>
using namespace std;

//typedef long long ll;

#define MY_PI acos(-1)
#define MY_MAX(a, b) ((a) > (b) ? (a) : (b))
#define MY_MIN(a, b) ((a) < (b) ? (a) : (b))
#define MY_MALLOC(n, type) ((type *)malloc((n) * sizeof(type)))
#define MY_ABS(a) (((a) >= 0) ? (a) : (-(a)))
#define MY_INT_MAX 0x7fffffff

/*==========================================================*\
| noip
\*==========================================================*/
struct segment
{
    int low;
    int high;
} seg[100005], tmp[100005];
bool cmp(segment a, segment b)
{
    return a.low < b.low;
}
int main()
{
    FILE *in, *out;
    in = freopen("dye.in", "r", stdin);
    out = freopen("dye.out", "w", stdout);
	int n;
	int i, j, k, a, b;
	int index = 1;
	char c;
	scanf("%d", &n);
	seg[0].low = 0;
	seg[0].high = 1000000000;
	for (k = 0; k < n; ++k) {
		scanf("%d%d %c", &a, &b, &c);
		if (c == 'w') {// , 
			int pos = 0;
			seg[index].low = a;
			seg[index].high = b;
			++index;
			sort(seg, seg + index, cmp);
			int t_low = seg[0].low;
			int t_high = seg[0].high;
			for (i = 0; i < index; ++i) {
				if (seg[i].low <= t_high) {
					if (seg[i].high > t_high) {
						t_high = seg[i].high;
					}
				} else {
					seg[pos].low = t_low;
					seg[pos++].high = t_high;
					t_low = seg[i].low;
					t_high = seg[i].high;
				}
			}
			seg[pos].low = t_low;
			seg[pos++].high = t_high;
			index = pos;
        } else {// , 
			int pos = 0;
			for (i = 0; i < index; ++i) {
				if (seg[i].high < a || seg[i].low > b) {
					tmp[pos].low = seg[i].low;
					tmp[pos].high = seg[i].high;
					++pos;
				} else if (seg[i].low >= a && seg[i].high <= b) {
					;
				} else if (seg[i].low >= a && seg[i].high > b) {
					tmp[pos].low = b + 1;
					tmp[pos].high = seg[i].high;
					++pos;
				} else if (seg[i].low < a && seg[i].high <= b) {
					tmp[pos].low = seg[i].low;
					tmp[pos].high = a - 1;
					++pos;
				} else if (seg[i].low < a && seg[i].high > b) {
					tmp[pos].low = seg[i].low;
					tmp[pos].high = a - 1;
					++pos;
					tmp[pos].low = b + 1;
					tmp[pos].high = seg[i].high;
					++pos;
				}
			}
			for (i = 0; i < pos; ++i) {
				seg[i].low = tmp[i].low;
				seg[i].high = tmp[i].high;
			}
			index = pos;
		}		
    }
	int max = -1;
	int ans;
	for (i = 0; i < index; ++i) {
		int t = seg[i].high - seg[i].low;
		if (t > max) {
			max = t;
			ans = i;
		}
	}
	printf("%d %d
", seg[ans].low, seg[ans].high); system("pause"); return 0; } /* 4 1 999999997 b 40 300 w 300 634 w 43 47 b */