SEO
手册
游戏
WEB
字典
单词
在线工具
当前位置:
首页
/
IT
/
程序
/
Objective-C
/
【USACO】奶牛跑步2
【USACO】奶牛跑步2
1
#include<
set
>
2
#include
3
#include
4
#include
5
#include
6
#include
7
#include<
string
>
8
#include
9
#include
10
#include
11
#include
12
#include
13
#include
14
#define
maxn 100010
15
#define
LL long long
16
#define
inf 999999999999999995ll
17
using
namespace
std;
18
int
ch[maxn][
2
],pre[maxn],size[maxn],root=
0
,tot=
0
;
19
LL ANS=
0
,key[maxn],
in
[maxn];
20
void
updata(
int
x){
21
size[x]=size[ch[x][
0
]]+size[ch[x][
1
]]+
1
;
22
}
23
void
Rotate(
int
x,
int
kind){
24
int
y=
pre[x];
25
ch[y][!kind]=
ch[x][kind];
26
pre[ch[x][kind]]=
y;
27
if
(pre[y])
28
ch[pre[y]][ch[pre[y]][
1
]==y]=
x;
29
pre[x]=
pre[y];
30
ch[x][kind]=
y;
31
pre[y]=
x;
32
updata(y);
33
updata(x);
34
}
35
void
Splay(
int
r,
int
goal){
36
while
(pre[r]!=
goal){
37
if
(pre[pre[r]]==
goal)
38
Rotate(r,ch[pre[r]][
0
]==
r);
39
else
{
40
int
y=
pre[r];
41
int
kind=ch[pre[y]][
0
]==
y;
42
if
(ch[y][kind]==
r){
43
Rotate(r,!
kind);
44
Rotate(r,kind);
45
}
46
else
{
47
Rotate(y,kind);
48
Rotate(r,kind);
49
}
50
}
51
}
52
if
(goal==
0
) root=
r;
53
}
54
void
newnode(
int
&x,
int
fa,LL keyy){
55
x=++
tot;
56
pre[x]=
fa;
57
ch[x][
0
]=ch[x][
1
]=
0
;
58
key[x]=
keyy;
59
size[x]=
1
;
60
}
61
void
Insert(LL k){
62
while
(ch[root][key[root]<
k])
63
size[root]++,root=ch[root][key[root]<
k];
64
size[root]++
;
65
newnode(ch[root][key[root]<
k],root,k);
66
Splay(ch[root][key[root]
0
);
67
}
68
void
get_nex(
int
x,LL k,
int
&
ans){
69
if
(!x)
return
;
70
if
(key[x]<=k) ans=x,get_nex(ch[x][
1
],k,ans);
71
if
(key[x]>k) get_nex(ch[x][
0
],k,ans);
72
}
73
void
erase(
int
x){
74
int
nexx=ch[x][
1
];
75
while
(ch[nexx][
0
]) nexx=ch[nexx][
0
];
76
Splay(nexx,
0
);
77
if
(!ch[nexx][
1
]) pre[ch[nexx][
0
]]=
0
,root=ch[nexx][
0
];
78
else
{
79
pre[ch[nexx][
1
]]=
0
;
80
int
rt=ch[nexx][
1
];
81
while
(ch[rt][
0
]) rt=ch[rt][
0
];
82
pre[ch[nexx][
0
]]=
rt;
83
ch[rt][
0
]=ch[nexx][
0
];
84
}
85
}
86
void
solve(LL k){
87
int
nex1=
root;get_nex(root,k,nex1);
88
Splay(nex1,
0
);
89
if
(!size[ch[nex1][
1
]])
90
ANS++
;
91
else
erase(nex1);
92
updata(nex1);
93
}
94
int
main()
95
{
96
freopen(
"
!.in
"
,
"
r
"
,stdin);
97
freopen(
"
!.out
"
,
"
w
"
,stdout);
98
int
n;
99
LL v,t;
100
scanf(
"
%d%lld
"
,&n,&
t);
101
for
(
int
i=
1
;i<=n;i++
)
102
scanf(
"
%lld%lld
"
,&
in
[i],&v),
in
[i]+=v*
t;
103
newnode(root,
0
,-
inf);
104
for
(
int
i=n;i>=
1
;i--
){
105
solve(
in
[i]);
106
Insert(
in
[i]);
107
}
108
printf(
"
%lld\n
"
,ANS);
109
return
0
;
110
}
来源: http://www.bubuko.com/infodetail-2013596.html
与本文相关文章
BZOJ 1623 [Usaco2008 Open]Cow Cars 奶牛飞车:贪心
USACO 动归求组合数
洛谷P2840 [USACO20DEC]Moocast(gold)奶牛广播-金
USACO Chapter 1 Section 1.2
USACO 2006 November Gold Corn Fields
186. [USACO Oct08] 牧场旅行
USACO奶牛赛跑(逆序对)
[USACO10MAR]伟大的奶牛聚集
暂无,快来抢沙发吧!
更多
提交
验证码:
{uname}
{body}
最佳答案
{$v.body}
{fun date('Y-m-d',$v.time)}