Cerința

Agentul 007 a uitat cifrul seifului în care păstra documentele, însă ştie cum poate fi aflat. Are nişte cartonaşe pe care sunt notate n numere naturale distincte din intervalul [ a,b ]. Mai are o listă cu m numere naturale distincte care reprezintă anumite poziţii din şirul ordonat crescător al numerelor de pe cartonaşe. Însumând numerele aflate pe poziţiile din listă se determină un număr natural care reprezintă cifrul seifului. Cum Agentul 007 nu a mai programat din liceu, vă roagă pe voi să găsiţi cifrul în schimbul a 100 de … puncte.

Date de intrare

Fișierul de intrare memory007.in conține pe prima linie numerele n,m,a,b, pe a doua linie n numere naturale distincte separate prin spații reprezentând numerele de pe cartonaşe, iar pe a treia linie m numere naturale distincte reprezentând poziţiile din listă.

Date de ieșire

Fișierul de ieșire memory007.out va conține pe prima linie cifrul seifului.

Restricții și precizări

• 1 ≤ m ≤ n ≤ 500.000
• numerele de pe cartonaşe vor fi distincte şi mai mici decât 1.000.000.000
• numerele din listă vor fi naturale nenule, distincte şi mai mici sau egale cu n, ordonate crescător
• 1 ≤ a ≤ b ≤ 1.000.000.000
• n ≤ b - a ≤ 700.000

Exemplu

memory007.in

5 3 30 80
78 56 34 45 61
1 2 5

memory007.out

157

Explicație

Numerele de pe cartonaşe sunt 78,56,34,45,61 şi sunt din intervalul [ 30,80 ]. Ordonate crescător formează şirul 34,45,56,61,78. Numerele din listă, adică 1,2,5, ne spun că cifrul se obţine însumând numerele de pe poziţiile 1, 2 şi 5 din şirul ordonat crescător al numerelor de pe cartonaşe, adică cifrul este 34+45+78=157.

#include <bits/stdc++.h>

using namespace std;

ifstream fin("memory007.in");
ofstream fout("memory007.out");

bitset<700020> v ;
long n , m , a , b , i , j , nr , x ;
long long suma , r , t ;

int main()
{
    fin >> n >> m >> a >> b ;
    for ( i=1 ; i<=n ; i++ )
    {
        fin >> x ;
        j = x-a ;
        v[j] = 1 ;
    }
    j = 0 ;
    nr = 0 ;
    suma = 0 ;
    for ( i=1 ; i<=m ; i++)
    {
        fin >> x ;
        while ( nr < x )
        {
          nr = nr + v[j] ;
          j++ ;
        }
        suma = suma + j - 1 ;
    }
    r = m ;
    t = a ;
    suma = suma + r * t ;
    fout << suma ;
    return 0;
}