- 学姐的钱包
-
woop115789 LV 7 @ 2015-04-07 16:31:27
按照题目的N大小只有40分，把空间调大了一点就过了
2 条评论
-
doc LV 10 MOD @ 2015-04-08 02:26:01
数据范围没有问题。就是100,000。
-
@ 2015-04-09 15:22:17
能不能把后几个点私信给我
-
@ 2015-04-09 23:48:41
不能公开数据呀 >_< 您可以自己随机一些极限数据看看呀。
-
@ 2015-04-11 08:17:13
要是极限数据有用就不找你了=。=
-
@ 2015-04-11 17:25:32
http://pan.baidu.com/s/1mg7lUbA
这里有一组我随机的极限数据。你提交的那份在vijos上得到40分的程序，我本机跑出来的答案也是不对的。
-
@ 2015-04-14 17:06:36
额，在我的机子上跑是对的，是不是系统的原因。。。麻烦了
-
-
@ 2015-04-07 16:40:19
Block code
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;struct Change{
int x , y , z , s1 , s2;
};const int N = 100010;
Change a1[4 * N] , a2[4 * N];
LL f[8 * N] , ans;
int t;bool Dox(Change A , Change B){return A.x < B.x;}
LL Min(LL x , LL y){
if (x == -1) return y;
if (y == -1) return x;
return min(x , y);
}LL Ask(int s , int l , int r , int x , int y){
if (l == x && r == y) return f[s];
int mid = (l + r) / 2;
if (y <= mid) return Ask(s * 2 , l , mid , x , y);
else if (x > mid) return Ask(s * 2 + 1 , mid + 1 , r , x , y);
else return Min(Ask(s * 2 , l , mid , x , mid) , Ask(s * 2 + 1 , mid + 1 , r , mid + 1 , y));
}void Putin(int s , int l , int r , int x , LL z){
if (l == x && r == x){
f[s] = Min(z , f[s]);
return;
}
int mid = (l + r) / 2;
if (x <= mid) Putin(s * 2 , l , mid , x , z);
else Putin(s * 2 + 1 , mid + 1 , r , x , z);
f[s] = Min(f[s * 2] , f[s * 2 + 1]);
}void Work(){
int n , m;
scanf("%d %d" , &n , &m);
memset(a1 , 0 , sizeof(a1));
memset(a2 , 0 , sizeof(a2));
int t = 0;
for(int i = 1; i <= n; i ++)
scanf("%d %d %d" , &a1[i].x , &a1[i].y , &a1[i].z);
if (m == 1){
ans = 0;
return;
}
sort(a1 + 1 , a1 + 1 + n , Dox);
for(int i = 1; i <= n; i ++){
a2[i].x = a1[i].x; a2[i + n].x = a1[i].y;
a2[i].s1 = i; a2[i].s2 = 1;
a2[i + n].s1 = i; a2[i + n].s2 = 2;
}
sort(a2 + 1 , a2 + 1 + 2 * n , Dox);
t = 1; int last = 1; bool bb = 1;
for(int i = 1; i <= 2 * n; i ++){
if (a2[i].x != last){
t ++;
if (bb && a2[i].x >= m){
bb = 0;
m = t;
if (a2[i].x > m) t ++;
}
last = a2[i].x;
}
if (a2[i].s2 == 1) a1[a2[i].s1].x = t;
else a1[a2[i].s1].y = t;
}
memset(f , 255 , sizeof(f));
Putin(1 , 1 , t , 1 , 0);
a1[0].x = 1; ans = -1;
bb = 1;
for(int i = 1; i <= n; i ++) if (a1[i].y == 1){
bb = 0;
}
for(int i = 1; i <= n; i ++){
LL tt = -1;
if (a1[i - 1].x >= a1[i].y) tt = Ask(1 , 1 , t , a1[i].y , a1[i - 1].x);
if (tt != -1){
tt += a1[i].z;
Putin(1 , 1 , t , a1[i].x , tt);
if (a1[i].x >= m) ans = Min(ans , tt);
}
}
ans = ans;
}int main(){
freopen("a.in" , "r" , stdin);
freopen("a.out" , "w" , stdout);scanf("%d" , &t);
for(int i = 1; i <= t; i ++){
Work();
printf("Case #%d: %lld\n" , i , ans);
}return 0;
}这个是代码 原来的a1 ， a2 ， f的范围分别是 N , 2 * N , 4 * N
- 1