908F.New Year and Rainbow Roads[贪心]

Roy and Biv have a set of n points on the infinite number line.

Each point has one of 3 colors: red, green, or blue.

Roy and Biv would like to connect all the points with some edges. Edges can be drawn between any of the two of the given points. The cost of an edge is equal to the distance between the two points it connects.

They want to do this in such a way that they will both see that all the points are connected (either directly or indirectly).

However, there is a catch: Roy cannot see the color red and Biv cannot see the color blue.

Therefore, they have to choose the edges in such a way that if all the red points are removed, the remaining blue and green points are connected (and similarly, if all the blue points are removed, the remaining red and green points are connected).

Help them compute the minimum cost way to choose edges to satisfy the above constraints.

Input

The first line will contain an integer n (1 ≤ n ≤ 300 000), the number of points.

The next n lines will contain two tokens p**i and c**i (p**i is an integer, 1 ≤ p**i ≤ 109, c**i is a uppercase English letter ‘R’, ‘G’ or ‘B’), denoting the position of the i-th point and the color of the i-th point. ‘R’ means red, ‘G’ denotes green, and ‘B’ means blue. The positions will be in strictly increasing order.

Output

Print a single integer, the minimum cost way to solve the problem.

Examples

input

1
2
3
4
5
4
1 G
5 R
10 B
15 G

output

1
23

input

1
2
3
4
5
4
1 G
2 R
3 B
10 G

output

1
12

Note

In the first sample, it is optimal to draw edges between the points (1,2), (1,4), (3,4). These have costs 4, 14, 5, respectively.

Solution

想出来没打完,是我太菜了,代码能力不行。

最开始被误导是网络流?然后看这范围应该是排序+贪心,然后都不用排序的

很显然,B和R连起来没用,无论是删B还是R,G都要连在一起。

所以就只有两种情况了,

  1. 两个G之间的所有的B和R,连到两端的G,间隔最大的地方空掉(B和R互不影响),也就是3×两个G之间的距离-最大的间隔(B和B的,R和R的分开),相邻的G和G相连
  2. 两头的G和所有的B连一起,两头的G和所有的R连一起,也就是2×两个相邻的G之间的距离

两头的随便搞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) x=y;}
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
int Map[300],n,bj[3];
int a[301000];
int b[301000];
int f[5],Max[5],last[5];
char ch;
long long ans;
int main()
{
Map['G']=0;Map['R']=1;Map['B']=2;
n=read();
for (int i=1;i<=n;i++) {a[i]=read();ch=getchar();b[i]=Map[(int)ch];}
int L=1,R=n;
while (b[L]&&L<=n)//头和尾单独处理
{
if (!f[b[L]]) {ans-=a[L];f[b[L]]=1;}
L++;
}
ans+=(long long)a[L]*(f[1]+f[2]);
f[1]=f[2]=f[0]=0;
while (b[R]&&R>=1)
{
if (!f[b[R]]) {ans-=a[n]-a[R];f[b[R]]=1;}
R--;
}
ans+=(long long)(a[n]-a[R])*(f[1]+f[2]);
memset(f,0,sizeof(f));
while (L<R)//处理相邻的G
{
int l=L,r=l+1;
while (b[r]&&r<=n) r++;if (r>n) break;
last[1]=last[2]=a[l];
Max[1]=0;Max[2]=Max[1];bj[1]=bj[2]=0;
for (int i=l+1;i<=r;i++)
{
for (int j=1;j<=2;j++)
if (b[i]!=j)
{
bj[j]=1;//找最大间隔
Max[j]=max(Max[j],a[i]-last[j]);last[j]=a[i];
}
}
ans+=min(2LL*(a[r]-a[l]),3LL*(a[r]-a[l])-Max[1]-Max[2]);
L=r;
}
printf("%I64d\n",ans);
return 0;
}