QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#572113 | #5082. Frog Jump | daxinghao# | WA | 1ms | 7808kb | C++14 | 1.3kb | 2024-09-18 12:04:49 | 2024-09-18 12:04:50 |
Judging History
answer
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
struct Interval
{
int s, e;
int idx;
};
bool cmp(Interval i1, Interval i2)
{
return i1.s < i2.s;
}
int loc[100005];
int cnt[100005];
int dis[100005];
int N, K;
Interval val[100005];
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> val[i].s >> val[i].e;
val[i].idx = i;
}
sort(val + 1, val + N + 1, cmp);
int mx = -1, phase = 0;
for (int i = 1; i <= N; i++) {
if (mx < val[i].s) {
dis[phase] = val[i].s - mx;
phase++;
}
mx = max(mx, val[i].e);
loc[val[i].idx] = phase;
}
//dis[i]: group i ~ group i+1 distance
int prv; cin >> prv;
for (int i = 2; i <= K; i++) {
int x; cin >> x;
if (loc[prv] < loc[x]) {
cnt[loc[prv]]++;
cnt[loc[x]]--;
}
else if (loc[prv] > loc[x]) {
cnt[loc[x]]++;
cnt[loc[prv]]--;
}
prv = x;
}
for (int i = 2; i <= phase-1; i++) cnt[i] += cnt[i-1];
int ans = 0;
for (int i = 1; i <= phase-1; i++) {
ans += cnt[i] * dis[i];
}
cout << ans << '\n';
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7808kb
input:
4 3 0 2 0 3 3 5 6 7 4 2 3
output:
1
result:
wrong answer 1st lines differ - expected: '2', found: '1'