Question

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.

Answer 1

#include <fstream>
#include <bitset>

using namespace std;

ifstream f("memory007.in");
ofstream g("memory007.out");

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

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