QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#780031 | #5082. Frog Jump | vwxyz | WA | 0ms | 3816kb | C++23 | 1.3kb | 2024-11-24 23:48:20 | 2024-11-24 23:48:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
template <class T>
pair<unordered_map<T,int>,vector<T>> Compress(vector<T> A){
vector<T> decomp=A;
sort(decomp.begin(),decomp.end());
decomp.erase(unique(decomp.begin(),decomp.end()),decomp.end());
unordered_map<T,int> comp;
for(int i=0;i<decomp.size();i++){
comp[decomp[i]]=i;
}
return {comp,decomp};
}
int main(){
int N,K;
cin>>N>>K;
vector<int> L(N),R(N),I(K);
for(int i=0;i<N;i++){
cin>>L[i]>>R[i];
}
for(int k=0;k<K;k++){
cin>>I[k];
I[k]-=1;
}
vector<int> LR;
LR.insert(LR.end(),L.begin(),L.end());
LR.insert(LR.end(),R.begin(),R.end());
auto [comp,decomp]=Compress(LR);
int le=comp.size();
vector<int> imos(le);
for(int i=0;i<N;i++){
imos[comp[L[i]]]+=1;
imos[comp[R[i]]]-=1;
}
for(int i=1;i<le;i++){
imos[i]+=imos[i-1];
}
vector<int> C(le);
for(int i=0;i<le-1;i++){
if(imos[i]==0){
C[i+1]=decomp[i+1]-decomp[i];
}
}
for(int i=1;i<le;i++){
C[i]+=C[i-1];
}
ll ans=0;
for(int k=0;k<K;k++){
ans+=abs(C[comp[L[I[k]]]]-C[comp[L[I[(k+1)%K]]]]);
}
cout<<ans<<"\n";
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
4 3 0 2 0 3 3 5 6 7 4 2 3
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
4 3 0 2 0 3 3 5 6 7 2 3 2
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
8 5 1 8 2 4 5 11 13 15 15 17 16 18 19 22 20 22 3 7 4 6 3
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
8 5 1 5 5 10 10 15 15 20 20 25 25 30 30 35 35 40 3 7 4 6 3
output:
0
result:
ok single line: '0'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3768kb
input:
10 7 1 5 5 10 10 15 15 20 20 25 25 30 30 35 35 40 41 50 50 60 3 7 4 6 3 9 10
output:
2
result:
wrong answer 1st lines differ - expected: '1', found: '2'