Cod sursa(job #1035486)

Utilizator ericptsStavarache Petru Eric ericpts Data 18 noiembrie 2013 16:57:25
Problema Dtcsu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 100000;
const int buff_len = 1024*8;
const int lines = 276997;

typedef long long LL;

LL v[MAX_N];

char buff_query[buff_len];
char buff_numeros[buff_len];

char *at_query = buff_query;
char *at_nums = buff_numeros;

FILE * query = fopen("dtcsu.in", "r");
FILE * numeros = fopen("dtcsu.in", "r");

void get_query_start(){
    int cnt = 0, i;
    int last = 0;
    char * buff = buff_query;

    while(cnt < lines){
        memset(buff, 0, buff_len);
        fread(buff, 1, buff_len, query);
        for(i = 0 ; i < buff_len && buff[i] && cnt < lines ; ++i){
            if(buff[i] == '\n')
                ++cnt;
            if(cnt == lines)
                break;
        }

        if(cnt < lines)
            last = ftell(query);
    }

    rewind(query);
    fseek(query, last, SEEK_SET);
    fread(buff_query, 1, i + 1, query);
    fread(buff_query, 1, buff_len, query);
    at_query = buff_query;
}

inline void next_char(char * &at){
    ++at;
    if(at - buff_query == buff_len){
        fread(buff_query, 1, buff_len, query);
        at = buff_query;
    } else if(at - buff_numeros == buff_len){
        fread(buff_numeros, 1, buff_len, numeros);
        at = buff_numeros;
    }
}

inline LL const next_int(char * &at){

    while(*at && (*at > '9' || *at < '0'))
        next_char(at);

    LL ret = 0;
    while(*at >= '0' && *at <= '9'){
        ret = ret * 10 + *at - 48;
        next_char(at);
    }
    return ret;
}

int n_len;

int bsearch(const LL &val){
    int step;
    int i0 = -1, i1 = -1;

    for(step = 1 ; step <= n_len ; step <<= 1);

    for(; step ; step >>= 1){
        if(i0 + step < n_len && v[i0 + step] <= val)
            i0 += step;
        if(i1 + step < n_len && v[i1 + step] < val)
            i1 += step;
    }

    return i0 - i1;
}

int check(){
    at_nums = buff_numeros;
    rewind(numeros);
    fread(buff_numeros, 1, buff_len, numeros);
    int ret = 0;
    for(int i = 0 ; i < lines ; ++i){
        LL const now = next_int(at_nums);
        ret += bsearch(now);
    }
    return ret;
}
int main()
{
    get_query_start();

    int Q = next_int(at_query);

    int i,j;
    int total = 0;
    for(i = 0 ; i < Q ; i += j){
        for(j = 0 ; j < MAX_N && i + j < Q ; ++j)
            v[j] = next_int(at_query);
        sort(v, v + j);

        n_len = j;
        total += check();
    }

    FILE * out = fopen("dtcsu.out", "r");
    fprintf(out, "%d\n", total);
    printf("%d\n", total);

    fclose(out);
    fclose(query);
    fclose(numeros);
    return 0;
}