ural 1019.Line Painting
http://acm.timus.ru/problem.aspx?space=1&num=1019
えっと、線分の木の題を探して、URALこれを見ました.水ですね.まだ染色の問題ですが、問題をよく見ていません.The segment of numerical axis from 0 to 10^9 is painted into whiteカラー.これは0から10^9まで白に染めてください.私は気をつけていません.昨夜は寮に帰りましたが、あまり元気がありませんでした.先ほどはちょっと調べれば過ぎました.
数字が大きいので、離散化を採用します.(試合なら、この問題は線分樹を使わない!!!直接離散化すれば大丈夫です.
境界に注意してください.他には何もありません.また、一番長い線分を統計する時は、スキャンして、ずっと色だったら、ずっと掃除します.
えっと、線分の木の題を探して、URALこれを見ました.水ですね.まだ染色の問題ですが、問題をよく見ていません.The segment of numerical axis from 0 to 10^9 is painted into whiteカラー.これは0から10^9まで白に染めてください.私は気をつけていません.昨夜は寮に帰りましたが、あまり元気がありませんでした.先ほどはちょっと調べれば過ぎました.
数字が大きいので、離散化を採用します.(試合なら、この問題は線分樹を使わない!!!直接離散化すれば大丈夫です.
境界に注意してください.他には何もありません.また、一番長い線分を統計する時は、スキャンして、ずっと色だったら、ずっと掃除します.
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#define MID(x,y) ((x+y)>>1)
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
using namespace std;
const int MAX = 10010;
int x[MAX];
struct Tnode{int l,r;int col;};
struct NODE{int x,y;bool col;};
NODE nn[MAX];
Tnode node[MAX*4];
int col[MAX];
void init()
{
for(int i=0; i<MAX; i++)
col[i] = 1;
memset(nn,0,sizeof(nn));
memset(node,0,sizeof(node));
}
void Build(int t,int l,int r)
{
node[t].l = l; node[t].r = r;
node[t].col = 1;
if( l == r - 1 ) return ;
int mid = MID(l,r);
Build(L(t),l,mid);
Build(R(t),mid,r);
}
void Updata(int t,int l,int r,int col)
{
if( node[t].l == l && node[t].r == r )
{
node[t].col = col;
return ;
}
if( node[t].col >= 0 && node[t].col != col )
{
node[R(t)].col = node[L(t)].col = node[t].col;
node[t].col = -1;
}
int mid = MID(node[t].l,node[t].r);
if( l >= mid )
Updata(R(t),l,r,col);
else
if( r <= mid )
Updata(L(t),l,r,col);
else
{
Updata(L(t),l,mid,col);
Updata(R(t),mid,r,col);
}
}
void Query(int t,int l,int r)
{
if( node[t].col >= 0 )
{
for(int i=node[t].l; i<node[t].r; i++)
col[i] = node[t].col;
return ;
}
int mid = MID(node[t].l,node[t].r);
if( l >= mid )
Query(R(t),l,r);
else
if( r <= mid )
Query(L(t),l,r);
else
{
Query(L(t),l,mid);
Query(R(t),mid,r);
}
}
void solve(int *x,int cnt,int n)
{
Build(1,0,cnt);
for(int i=0; i<n; i++)
{
int xx = lower_bound(x,x+cnt,nn[i].x) - x;
int yy = lower_bound(x,x+cnt,nn[i].y) - x;
Updata(1,xx,yy,nn[i].col);
}
Query(1,0,cnt);
int s = 0,e = 0,te,ts;
int mmax = 0;
col[cnt] = 0;
x[cnt] = 1000000000;
for(int i=0; i<cnt; i++)
{
ts = x[i];
while( col[i] == 1 )
i++;
te = x[i];
if( te - ts > e - s )
{
e = te;
s = ts;
}
}
printf("%d %d
",s,e);
}
int main()
{
int n;
char s[5];
while( ~scanf("%d",&n) )
{
int cnt = 0;
init();
nn[0].x = 0; nn[0].y = 1000000000;
nn[0].col = 1;
x[cnt++] = nn[0].x; x[cnt++] = nn[0].y;
for(int i=1; i<=n; i++)
{
scanf("%d%d%s",&nn[i].x,&nn[i].y,s);
x[cnt++] = nn[i].x;
x[cnt++] = nn[i].y;
if( s[0] == 'w' )
nn[i].col = 1;
}
sort(x,x+cnt);
cnt = unique(x,x+cnt) - x;
solve(x,cnt,n+1);
}
return 0;
}