34dd53bac9 2012-06-07 kinaba: #include <iostream> 34dd53bac9 2012-06-07 kinaba: #include <sstream> 34dd53bac9 2012-06-07 kinaba: #include <iomanip> 34dd53bac9 2012-06-07 kinaba: #include <vector> 34dd53bac9 2012-06-07 kinaba: #include <string> 34dd53bac9 2012-06-07 kinaba: #include <map> 34dd53bac9 2012-06-07 kinaba: #include <set> 34dd53bac9 2012-06-07 kinaba: #include <algorithm> 34dd53bac9 2012-06-07 kinaba: #include <numeric> 34dd53bac9 2012-06-07 kinaba: #include <iterator> 34dd53bac9 2012-06-07 kinaba: #include <functional> 34dd53bac9 2012-06-07 kinaba: #include <complex> 34dd53bac9 2012-06-07 kinaba: #include <queue> 34dd53bac9 2012-06-07 kinaba: #include <stack> 34dd53bac9 2012-06-07 kinaba: #include <cmath> 34dd53bac9 2012-06-07 kinaba: #include <cassert> 34dd53bac9 2012-06-07 kinaba: #include <memory> 34dd53bac9 2012-06-07 kinaba: using namespace std; 34dd53bac9 2012-06-07 kinaba: typedef long long LL; 34dd53bac9 2012-06-07 kinaba: typedef long double LD; 34dd53bac9 2012-06-07 kinaba: typedef complex<LD> CMP; 34dd53bac9 2012-06-07 kinaba: 34dd53bac9 2012-06-07 kinaba: template<typename T=LL> 34dd53bac9 2012-06-07 kinaba: struct FenwickTree 34dd53bac9 2012-06-07 kinaba: { 34dd53bac9 2012-06-07 kinaba: vector<T> x; 34dd53bac9 2012-06-07 kinaba: FenwickTree(size_t n) : x(n) {} 34dd53bac9 2012-06-07 kinaba: 34dd53bac9 2012-06-07 kinaba: void incr( int k, const T& a ) { // z[k] += a; 34dd53bac9 2012-06-07 kinaba: for(; k < x.size(); k|=k+1) 34dd53bac9 2012-06-07 kinaba: x[k] += a; 34dd53bac9 2012-06-07 kinaba: } 34dd53bac9 2012-06-07 kinaba: T sum(int i, int j) { // Sigma z[i,j) excl. 34dd53bac9 2012-06-07 kinaba: return sum_impl(j-1) - sum_impl(i-1); 34dd53bac9 2012-06-07 kinaba: } 34dd53bac9 2012-06-07 kinaba: T sum_impl(int j) { // Sigma z[0,j] incl. 34dd53bac9 2012-06-07 kinaba: T v = T(); 34dd53bac9 2012-06-07 kinaba: for(; j>=0; j=(j&(j+1))-1) 34dd53bac9 2012-06-07 kinaba: v += x[j]; 34dd53bac9 2012-06-07 kinaba: return v; 34dd53bac9 2012-06-07 kinaba: } 34dd53bac9 2012-06-07 kinaba: }; 34dd53bac9 2012-06-07 kinaba: 34dd53bac9 2012-06-07 kinaba: template<typename T> 34dd53bac9 2012-06-07 kinaba: std::vector<int> compress(std::vector<T>& xs) 34dd53bac9 2012-06-07 kinaba: { 34dd53bac9 2012-06-07 kinaba: std::vector< pair<T,int> > xi; 34dd53bac9 2012-06-07 kinaba: for(int i=0; i<xs.size(); ++i) 34dd53bac9 2012-06-07 kinaba: xi.push_back( make_pair(xs[i], i) ); 34dd53bac9 2012-06-07 kinaba: sort(xi.begin(), xi.end()); 34dd53bac9 2012-06-07 kinaba: 34dd53bac9 2012-06-07 kinaba: std::vector<int> result(xs.size()); 34dd53bac9 2012-06-07 kinaba: for(int k=0; k<xi.size(); ++k) 34dd53bac9 2012-06-07 kinaba: result[xi[k].second] = k; 34dd53bac9 2012-06-07 kinaba: return result; 34dd53bac9 2012-06-07 kinaba: } 34dd53bac9 2012-06-07 kinaba: 34dd53bac9 2012-06-07 kinaba: class ThreePoints { public: 34dd53bac9 2012-06-07 kinaba: long long countColoring(int N, 34dd53bac9 2012-06-07 kinaba: int xzero, int xmul, int xadd, int xmod, 34dd53bac9 2012-06-07 kinaba: int yzero, int ymul, int yadd, int ymod) 34dd53bac9 2012-06-07 kinaba: { 34dd53bac9 2012-06-07 kinaba: vector<int> x(N), y(N); 34dd53bac9 2012-06-07 kinaba: x[0] = xzero; for(int i=1; i<N; ++i) x[i] = (x[i-1] * LL(xmul) + xadd) % xmod; 34dd53bac9 2012-06-07 kinaba: y[0] = yzero; for(int i=1; i<N; ++i) y[i] = (y[i-1] * LL(ymul) + yadd) % ymod; 34dd53bac9 2012-06-07 kinaba: x = compress(x); 34dd53bac9 2012-06-07 kinaba: y = compress(y); 34dd53bac9 2012-06-07 kinaba: 34dd53bac9 2012-06-07 kinaba: vector< pair<int,int> > y_desc; 34dd53bac9 2012-06-07 kinaba: for(int i=0; i<N; ++i) 34dd53bac9 2012-06-07 kinaba: y_desc.push_back(make_pair(y[i], x[i])); 34dd53bac9 2012-06-07 kinaba: sort(y_desc.rbegin(), y_desc.rend()); 34dd53bac9 2012-06-07 kinaba: 34dd53bac9 2012-06-07 kinaba: LL result = 0; 34dd53bac9 2012-06-07 kinaba: FenwickTree<> p(N), sp(N); 34dd53bac9 2012-06-07 kinaba: for(int i=0; i<N; ++i) { 34dd53bac9 2012-06-07 kinaba: const int x = y_desc[i].second; 34dd53bac9 2012-06-07 kinaba: LL sp_ = p.sum(x+1, N); 34dd53bac9 2012-06-07 kinaba: LL ssp_ = sp.sum(x+1, N); 34dd53bac9 2012-06-07 kinaba: p.incr(x, 1); 34dd53bac9 2012-06-07 kinaba: sp.incr(x, sp_); 34dd53bac9 2012-06-07 kinaba: result += sp_*(sp_-1)/2 - ssp_; 34dd53bac9 2012-06-07 kinaba: } 34dd53bac9 2012-06-07 kinaba: return result; 34dd53bac9 2012-06-07 kinaba: } 34dd53bac9 2012-06-07 kinaba: }; 34dd53bac9 2012-06-07 kinaba: 34dd53bac9 2012-06-07 kinaba: // BEGIN CUT HERE 34dd53bac9 2012-06-07 kinaba: #include <ctime> 34dd53bac9 2012-06-07 kinaba: double start_time; string timer() 34dd53bac9 2012-06-07 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 34dd53bac9 2012-06-07 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 34dd53bac9 2012-06-07 kinaba: { os << "{ "; 34dd53bac9 2012-06-07 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 34dd53bac9 2012-06-07 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 34dd53bac9 2012-06-07 kinaba: void verify_case(const long long& Expected, const long long& Received) { 34dd53bac9 2012-06-07 kinaba: bool ok = (Expected == Received); 34dd53bac9 2012-06-07 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 34dd53bac9 2012-06-07 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 34dd53bac9 2012-06-07 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 34dd53bac9 2012-06-07 kinaba: #define END verify_case(_, ThreePoints().countColoring(N, xzero, xmul, xadd, xmod, yzero, ymul, yadd, ymod));} 34dd53bac9 2012-06-07 kinaba: int main(){ 34dd53bac9 2012-06-07 kinaba: 34dd53bac9 2012-06-07 kinaba: CASE(0) 34dd53bac9 2012-06-07 kinaba: int N = 9; 34dd53bac9 2012-06-07 kinaba: int xzero = 3; 34dd53bac9 2012-06-07 kinaba: int xmul = 8; 34dd53bac9 2012-06-07 kinaba: int xadd = 6; 34dd53bac9 2012-06-07 kinaba: int xmod = 11; 34dd53bac9 2012-06-07 kinaba: int yzero = 5; 34dd53bac9 2012-06-07 kinaba: int ymul = 7; 34dd53bac9 2012-06-07 kinaba: int yadd = 8; 34dd53bac9 2012-06-07 kinaba: int ymod = 11; 34dd53bac9 2012-06-07 kinaba: long long _ = 8LL; 34dd53bac9 2012-06-07 kinaba: END 34dd53bac9 2012-06-07 kinaba: CASE(1) 34dd53bac9 2012-06-07 kinaba: int N = 4; 34dd53bac9 2012-06-07 kinaba: int xzero = 9; 34dd53bac9 2012-06-07 kinaba: int xmul = 6; 34dd53bac9 2012-06-07 kinaba: int xadd = 8; 34dd53bac9 2012-06-07 kinaba: int xmod = 10; 34dd53bac9 2012-06-07 kinaba: int yzero = 4; 34dd53bac9 2012-06-07 kinaba: int ymul = 8; 34dd53bac9 2012-06-07 kinaba: int yadd = 5; 34dd53bac9 2012-06-07 kinaba: int ymod = 10; 34dd53bac9 2012-06-07 kinaba: long long _ = 2LL; 34dd53bac9 2012-06-07 kinaba: END 34dd53bac9 2012-06-07 kinaba: CASE(2) 34dd53bac9 2012-06-07 kinaba: int N = 20; 34dd53bac9 2012-06-07 kinaba: int xzero = 30; 34dd53bac9 2012-06-07 kinaba: int xmul = 3; 34dd53bac9 2012-06-07 kinaba: int xadd = 71; 34dd53bac9 2012-06-07 kinaba: int xmod = 100; 34dd53bac9 2012-06-07 kinaba: int yzero = 78; 34dd53bac9 2012-06-07 kinaba: int ymul = 12; 34dd53bac9 2012-06-07 kinaba: int yadd = 50; 34dd53bac9 2012-06-07 kinaba: int ymod = 100; 34dd53bac9 2012-06-07 kinaba: long long _ = 263LL; 34dd53bac9 2012-06-07 kinaba: END 34dd53bac9 2012-06-07 kinaba: CASE(3) 34dd53bac9 2012-06-07 kinaba: int N = 300000; 34dd53bac9 2012-06-07 kinaba: int xzero = 99097861; 34dd53bac9 2012-06-07 kinaba: int xmul = 102766912; 34dd53bac9 2012-06-07 kinaba: int xadd = 95284952; 34dd53bac9 2012-06-07 kinaba: int xmod = 123456789; 34dd53bac9 2012-06-07 kinaba: int yzero = 443104491; 34dd53bac9 2012-06-07 kinaba: int ymul = 971853214; 34dd53bac9 2012-06-07 kinaba: int yadd = 569775557; 34dd53bac9 2012-06-07 kinaba: int ymod = 987654321; 34dd53bac9 2012-06-07 kinaba: long long _ = 749410681185726LL; 34dd53bac9 2012-06-07 kinaba: END 34dd53bac9 2012-06-07 kinaba: /* 34dd53bac9 2012-06-07 kinaba: CASE(4) 34dd53bac9 2012-06-07 kinaba: int N = ; 34dd53bac9 2012-06-07 kinaba: int xzero = ; 34dd53bac9 2012-06-07 kinaba: int xmul = ; 34dd53bac9 2012-06-07 kinaba: int xadd = ; 34dd53bac9 2012-06-07 kinaba: int xmod = ; 34dd53bac9 2012-06-07 kinaba: int yzero = ; 34dd53bac9 2012-06-07 kinaba: int ymul = ; 34dd53bac9 2012-06-07 kinaba: int yadd = ; 34dd53bac9 2012-06-07 kinaba: int ymod = ; 34dd53bac9 2012-06-07 kinaba: long long _ = LL; 34dd53bac9 2012-06-07 kinaba: END 34dd53bac9 2012-06-07 kinaba: CASE(5) 34dd53bac9 2012-06-07 kinaba: int N = ; 34dd53bac9 2012-06-07 kinaba: int xzero = ; 34dd53bac9 2012-06-07 kinaba: int xmul = ; 34dd53bac9 2012-06-07 kinaba: int xadd = ; 34dd53bac9 2012-06-07 kinaba: int xmod = ; 34dd53bac9 2012-06-07 kinaba: int yzero = ; 34dd53bac9 2012-06-07 kinaba: int ymul = ; 34dd53bac9 2012-06-07 kinaba: int yadd = ; 34dd53bac9 2012-06-07 kinaba: int ymod = ; 34dd53bac9 2012-06-07 kinaba: long long _ = LL; 34dd53bac9 2012-06-07 kinaba: END 34dd53bac9 2012-06-07 kinaba: */ 34dd53bac9 2012-06-07 kinaba: } 34dd53bac9 2012-06-07 kinaba: // END CUT HERE