Artifact Content
Not logged in

Artifact 237d262a30af71675004f995fe6908b9ba981381


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

static const LL MODVAL = 1000000007LL;
LL ADD(LL x, LL y) { return (x+y)%MODVAL; }
LL MUL(LL x, LL y) { return (x*y)%MODVAL; }

class MegaSum { public:
	int calculate(long long N) 
	{
		LL nth = sq(N);
		pair<LL,LL> p = position_of(N);

		LL cnt = 0;
		for(LL lane=1; lane<=nth; ++lane)
			cnt = ADD(cnt, sum_in_the_lane(p, lane));
		return cnt;
	}

	LL sq( LL N )
	{
		LL nth=1;
		while( !(N <= nth*nth) )
			++nth;
		return nth;
	}

	pair<LL,LL> position_of( LL N )
	{
		// in which lane?
		LL nth = sq(N);

		// position
		LL dif = N - (nth-1)*(nth-1);
		LL y = (dif<=nth ? dif : nth);
		LL x = (dif<=nth ? nth : nth+nth-dif);
		if( nth%2 == 1 ) swap(x, y);

		return make_pair(y,x);
	}

	LL sum_in_the_lane(pair<LL,LL> p, LL lane)
	{
		LL y = p.first;
		LL x = p.second;


		if( lane%2 == 0 )
		{
			//     V
			//     V
			//<<<<<<
			LL s = lane<=x ? sumV( 1, lane, min(y,lane), lane, y, x ) : 0;
			s = ADD(s, lane<=y ? sumH(lane,min(x,lane-1),lane,1,y,x) : 0);
			return s;
		}
		else
		{
			//     A
			//     A
			//>>>>>>
			LL s = lane<=y ? sumH( lane, 1, lane, min(x,lane), y, x ) : 0;
			s = ADD(s, lane<=x ? sumV(min(y,lane-1),lane,1,lane,y,x) : 0);
			return s;
		}
	}

	LL value_of(LL y, LL x)
	{
		LL lane = max(x, y);
		return (lane-1)*(lane-1) + (lane%2==0 ? (y<lane ? y : lane+lane-x)
		                                      : (x<lane ? x : lane+lane-y));
	}

	LL sumH(LL y0, LL x, LL y1, LL _, LL Y, LL X)
	{
		// \Sigma value_of(y0+i,x) * (X-x+1)*(Y-(y0+i)+1)
		//=
		// \Sigma (value_of(y0,x)+i) * (X-x+1)*(Y-(y0+i)+1)
		//=
		// \Sigma (V0            +i) * XX     *(YY-i)
		//=
		// ...
		assert(false);
	}

	LL sumV(LL y, LL x0, LL _, LL x1, LL Y, LL X)
	{
		assert(false);
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, MegaSum().calculate(N));}
int main(){

CASE(0)
	long long N = 8LL; 
	int _ = 58; 
END
CASE(1)
	long long N = 12LL; 
	int _ = 282; 
END
CASE(2)
	long long N = 11LL; 
	int _ = 128; 
END
CASE(3)
	long long N = 6LL; 
	int _ = 50; 
END
CASE(4)
	long long N = 34539LL; 
	int _ = 437909839; 
END
CASE(5)
	long long N = 10000000000LL; 
	int _ = -1; 
END
CASE(6)
	long long N = 123456789LL; 
	int _ = -1; 
END

}
// END CUT HERE