# Cod sursa(job #2421036)

Utilizator Data 13 mai 2019 22:37:01 Fibo3 0 cpp-64 done Arhiva de probleme 2.17 kb
``````#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <string>
#include <unordered_set>

using namespace std;

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

int64_t n;
int64_t sx, sy, fx, fy;

unordered_set<int64_t> fibo;
vector<int64_t> flist;

int countRow(int64_t r, int64_t l) {
int res = 0;
int i = 0;
while ((l + r) >= flist[i]) {

if (flist[i] >= r) {
res++;
}

i++;
}
return res;
}

int64_t rightExit(int64_t r, int64_t l) {
int i = 0;
while ((l + r) > flist[i]) {
i++;
}

return flist[i] - l - r;
}

int64_t leftExit(int64_t r, int64_t l) {
int i = 0;
while ((l + r) >= flist[i]) {

if (flist[i] >= r) {
return flist[i] - r;
}

i++;
}
}

int solve(int64_t sx, int64_t sy, int64_t fx, int64_t fy) {
int sol = 0;
int64_t i = sy;

int64_t one = 1;

while (i <=fy) {

auto cnt = countRow(i, fx);
auto left = leftExit(i, fx);
auto right = rightExit(i, fx);

auto inc = left + 1;
inc = min(inc, fy - i + 1);
inc = min(inc, right);
inc = max(inc, one);

sol += cnt * inc;
i += inc;

}

return sol;
}

void brute() {
int sol = 0;
for (int64_t i = sx; i <= fx; ++i) {
for (int64_t j = sy; j <= fy; ++j) {
if (fibo.count(i + j)) {
sol++;
}
}
}
fout << sol << "\n";
}

void bruteCntR() {
int sol = 0;
for (int64_t i = sy; i <= fy; ++i) {
sol += countRow(i, fx);

}
fout << sol << "\n";
}

int main() {

fin >> n;

int64_t f1 = 1;
int64_t f2 = 1;

while (f2 < 5000000000000000ll) {
fibo.insert(f2);
flist.push_back(f2);
int64_t t = f1;
f1 = f2;
f2 = f2 + t;
}

for (int i = 0; i < n; ++i) {
fin >> sx >> sy >> fx >> fy;

auto s1 = solve(0, 0, fx, fy);
auto s2 = solve(0, 0, sx - 1, fy);
auto s3 = solve(0, 0, fx, sy - 1);
auto s4 = solve(0, 0, sx - 1, sy - 1);

fout << s1 + s4 - s2 - s3 << "\n";
}

//for (int64_t i = sx; i <= fx; ++i) {
//	for (int64_t j = sy; j <= fy; ++j) {
//		if (fibo.count(i + j)) {
//			fout << "#";
//		}
//		else {
//			fout << " ";
//		}
//	}
//	fout << "\n";
//}

return 0;
}``````