Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:不知道是我题读错了还是测试数据有问题

Posted by 1966412011 at 2019-10-06 23:14:55 on Problem 3171
In Reply To:不知道是我题读错了还是测试数据有问题 Posted by:1966412011 at 2019-10-06 23:13:57
```> 按照提上的意思，如果有第0秒，第0秒也应该有有牛，我有一份代码，测试数据
> 3 0 4
> 0 0 1
> 1 2 3
> 3 4 1
> 我的代码输出4，这个代码依然可以通过
#include <cstdio>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
//#include <unordered_map>

#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define l(x) x<<1
#define r(x) x<<1|1
#define ms(a,b) memset(a,b,sizeof(a))

using namespace std;

struct node {
int s;
int t;
int val;
};

bool cmp(const node& a, const node& b) {
return a.t < b.t;
}

int n, m, e;
int dp[90000];
node demo[11000];

const int MAX_N = 1 << 17;
int len, dat[2 * MAX_N - 1];

void init(int n_) {
len = 1;
while (len < n_)
len *= 2;

for (int i = 0; i < len * 2 - 1; i++)
dat[i] = INF;
}

void update(int k, int a) {
k += len - 1;
dat[k] = a;
while (k > 0) {
k = (k - 1) / 2;
dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}

int query(int a,int b,int k,int l,int r){
if (r <= a || b <= l)
return INF;

if (a <= l && r <= b) return dat[k];
else {
int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}

int query(int a, int b) {
return query(a, b, 0, 0, len);
}

int get(int k) {
return dat[k + len - 1];
}

int main(void) {
scanf("%d%d%d", &n, &m, &e);

for (int i = 0; i < n; i++) {
scanf("%d%d%d", &demo[i].s, &demo[i].t,&demo[i].val);
}
init(e);
update(m, 0);
sort(demo, demo + n,cmp);

ms(dp, INF);
dp[0] = 0;

for (int i = 0; i < n; i++) {
int v = min(dp[demo[i].t], query(demo[i].s - 1, demo[i].t+1)+ demo[i].val);
dp[demo[i].t] = v;
update(demo[i].t, v);
}

if(dp[e]!=INF)
printf("%d\n", dp[e]);
else
printf("-1\n");

return 0;
}
```

Followed by: