# Cod sursa(job #2426385)

Utilizator Data 27 mai 2019 17:56:57 Fibo3 100 cpp-64 done Arhiva de probleme 1.3 kb
``````#include <fstream>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int n;

#ifdef DEBUG
string name = "data";
#else
string name = "fibo3";
#endif

ifstream fin(name + ".in");
ofstream fout(name + ".out");

vector<int64_t> f;

int64_t countDiagonal(int64_t n, int64_t x, int64_t y) {

if (x >= n) {
return min(n + 1, y + 1);
}
if (y >= n) {
return min(n + 1, x + 1);
}

return max(x + y - n + 1, (int64_t)0ll);
}

int64_t query(int64_t x, int64_t y) {
auto fi = f[0];

int ndx = 0;

int64_t res = 0ll;

if (x > y) {
auto t = x;
x = y;
y = t;
}

while (fi <= y * 2) {
res += countDiagonal(fi, x, y);
ndx++;
fi = f[ndx];
}

return res;
}

int main() {

uint64_t t1 = 1;
uint64_t t2 = 1;

while (t2 < (int64_t)5000000000000000ll) {
f.push_back(t2);
int64_t aux = t1;
t1 = t2;
t2 = aux + t2;
}

fin >> n;

for (int i = 0; i < n; ++i) {
int64_t lx, ly, ux, uy;

fin >> lx >> ly >> ux >> uy;

fout << query(ux, uy) - query(lx - 1, uy) - query(ux, ly - 1) + query(lx - 1, ly - 1) << "\n";
}

return 0;
}
``````