QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#780031#5082. Frog JumpvwxyzWA 0ms3816kbC++231.3kb2024-11-24 23:48:202024-11-24 23:48:24

Judging History

你现在查看的是最新测评结果

  • [2024-11-24 23:48:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3816kb
  • [2024-11-24 23:48:20]
  • 提交

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'