Cod sursa(job #2166756)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 13 martie 2018 18:43:53
Problema Fibo3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#define VAL 85
#define INF 2000000000000000
#define LL long long

using namespace std;

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

LL M, N, i, j, ANS;
LL X1, Y1, X2, Y2, A, B;
LL F[VAL];

LL GetANS(LL X, LL Y)
{
    if (X<0 || Y<0)
      return 0;
    LL ANS=0;
    for (i=1; i<=M; i++)
    {
        if (F[i]<=min(X, Y))
        {
            ANS+=F[i]+1;
            continue;
        }
        if (F[i]>X+Y)
          break;
        if (F[i]==X+Y)
        {
            ANS++;
            continue;
        }
        A=F[i];
        B=F[i]-X;
        if (Y>=B)
          ANS+=min(Y, A)-B+1;
    }
    return ANS;
}

int main()
{
    fin >> N;
    F[0]=F[1]=M=1;
    for (i=2; i<VAL; i++)
    {
        M++;
        F[M]=F[M-1]+F[M-2];
        if (F[M]>INF)
          break;
    }
    while (N>0)
    {
        fin >> X1 >> Y1 >> X2 >> Y2;
        N--;
        ANS=GetANS(X2, Y2)+GetANS(X1-1, Y1-1);
        ANS-=GetANS(X1-1, Y2)+GetANS(X2, Y1-1);
        fout << ANS << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}