ADDED   SRM/TCO12-2C-U/1A.cpp
Index: SRM/TCO12-2C-U/1A.cpp
==================================================================
--- SRM/TCO12-2C-U/1A.cpp
+++ SRM/TCO12-2C-U/1A.cpp
@@ -0,0 +1,261 @@
+#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>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+class GreedyTravelingSalesman { public:
+	int worstDistance(vector <string> thousands, vector <string> hundreds, vector <string> tens, vector <string> ones)
+	{
+		int N = thousands.size();
+		vector< vector<int> > d(N, vector<int>(N));
+		for(int a=0; a<N; ++a)
+		for(int b=0; b<N; ++b)
+			d[a][b] = (thousands[a][b]-'0')*1000+(hundreds[a][b]-'0')*100+(tens[a][b]-'0')*10+(ones[a][b]-'0');
+
+		int worst = 0;
+		for(int a=0; a<N; ++a)
+		for(int b=0; b<N; ++b) {
+			const int t = d[a][b];
+
+			vector<int> cand = d[a];
+			for(int c=0; c<N; ++c) {
+				if(b>c && d[a][c]-1>=1)
+					cand.push_back(d[a][c]-1);
+			}
+			cand.push_back(1);
+			cand.push_back(9999);
+			for(int i=0; i<cand.size(); ++i) if(1<=cand[i]&&cand[i]<=9999){
+				d[a][b] = cand[i];
+				worst = max(worst, goGreedy(d, N));
+			}
+			d[a][b] = t;
+		}
+		return worst;
+	}
+
+	int goGreedy(vector< vector<int> >& d, int N)
+	{
+		vector<bool> v(N);
+		int p = 0;
+		int total = 0;
+		for(;;) {
+			v[p] = true;
+			vector< pair<int,int> > cand;
+			for(int q=0; q<N; ++q)
+				if(!v[q])
+					cand.push_back(make_pair(d[p][q],q));
+			if(cand.empty())
+				return total;
+			int q = min_element(cand.begin(), cand.end())->second;
+			total += d[p][q];
+			p = q;
+		}
+	}
+};
+
+// 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(_, GreedyTravelingSalesman().worstDistance(thousands, hundreds, tens, ones));}
+int main(){
+
+CASE(0)
+	string thousands_[] = {"055", "505", "550"};
+	  vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/sizeof(*thousands_)); 
+	string hundreds_[] = {"000", "000", "000"};
+	  vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 
+	string tens_[] = {"000", "000", "000"};
+	  vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); 
+	string ones_[] = {"000", "000", "000"};
+	  vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); 
+	int _ = 14999; 
+END
+CASE(1)
+	string thousands_[] = {"018", "101", "990"};
+	  vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/sizeof(*thousands_)); 
+	string hundreds_[] = {"000", "000", "990"};
+	  vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 
+	string tens_[] = {"000", "000", "990"};
+	  vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); 
+	string ones_[] = {"000", "000", "990"};
+	  vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); 
+	int _ = 17999; 
+END
+CASE(2)
+	string thousands_[] = {"00888", "00999", "00099", "00009", "00000"}
+;
+	  vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/sizeof(*thousands_)); 
+	string hundreds_[] = {"00000", "00999", "00099", "00009", "00000"}
+;
+	  vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 
+	string tens_[] = {"00000", "10999", "11099", "11109", "11110"}
+;
+	  vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); 
+	string ones_[] = {"01000", "00999", "00099", "00009", "00000"}
+;
+	  vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); 
+	int _ = 37997; 
+END
+CASE(3)
+	string thousands_[] = {"000000", "000000", "990999", "999099", "999909", "999990"};
+	  vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/sizeof(*thousands_)); 
+	string hundreds_[] = {"000000", "000000", "990999", "999099", "999909", "999990"};
+	  vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 
+	string tens_[] = {"000000", "000000", "990999", "999099", "999909", "999990"};
+	  vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); 
+	string ones_[] = {"011111", "101111", "990998", "999099", "999809", "999980"};
+	  vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); 
+	int _ = 39994; 
+END
+CASE(4)
+	string thousands_[] = {"00", "00"};
+	  vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/sizeof(*thousands_)); 
+	string hundreds_[] = {"00", "00"};
+	  vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 
+	string tens_[] = {"00", "00"};
+	  vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); 
+	string ones_[] = {"01", "10"};
+	  vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); 
+	int _ = 9999; 
+END
+CASE(5)
+	string thousands_[] = {"0930", "1064", "0104", "1070"};
+	  vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/sizeof(*thousands_)); 
+	string hundreds_[] = {"0523", "1062", "6305", "0810"};
+	  vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 
+	string tens_[] = {"0913", "0087", "3109", "1500"};
+	  vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); 
+	string ones_[] = {"0988", "2030", "6103", "5530"};
+	  vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); 
+	int _ = 14124; 
+END
+CASE(6)
+	string thousands_[] = {"0329", "2036", "2502", "8970"};
+	  vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/sizeof(*thousands_)); 
+	string hundreds_[] = {"0860", "5007", "0404", "2770"};
+	  vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 
+	string tens_[] = {"0111", "2087", "2009", "2670"};
+	  vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); 
+	string ones_[] = {"0644", "1094", "7703", "7550"};
+	  vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); 
+	int _ = 17785; 
+END
+CASE(7)
+	string thousands_[] = {"098444156277392825243100607342", "200097656837707947798866622385",
+"290231695687128834848596019656", "407026565077650435591867333275",
+"843401002617957470339040852874", "349970591997218853400632158696",
+"419933000593511123878416328483", "696294503254214847884399055978",
+"641473980706392541888675375279", "936720077098054565078142449625",
+"203476089500970673371115103717", "511071853860312304204656816567",
+"347105714685052402147763392257", "125122220860203856679947732062",
+"121462979669220132944063071653", "928254504048223043681383050365",
+"502607124708785202536036594373", "793596587517012870906900400361",
+"712360060935346182084840996318", "761671392040312345002273366240",
+"812935320276738878200716148806", "228506917464479046839069740872",
+"755395721473881083093906155745", "192597782177910118061710039501",
+"721382839206745793530453013267", "076061794267810491768114700256",
+"857528357758085424372388710251", "173322450800442594145600093043",
+"761667192345925280210514410800", "521229810525064090301842864060"};
+	  vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/sizeof(*thousands_)); 
+	string hundreds_[] = {"098270581534726237580246464451", "108829763716747148395013332067",
+"830061279541380758964430491222", "431005058477371114834129826284",
+"601807314489142917339949914290", "330640126699733151822328009407",
+"851821069798846354566780680271", "648888407535627630663351884365",
+"051398660825518466890170447894", "631934884097214069747147155777",
+"768071219404930950472885304916", "924954163330715847561718395488",
+"189910033179029204426829479070", "960645776060701332402794474433",
+"244875842263950931884758650019", "528470075229660077692189442311",
+"752198673046476808978058423064", "899325998610605600525587569431",
+"965750123741820904031880230236", "121658852172052167706008445728",
+"556199378085507717770434101126", "864838242791403197110088834005",
+"593435343245223500439707230479", "622529771475840345624500421425",
+"503486612623475041392122088159", "518334626169655694269507400008",
+"967091631529233593414345370288", "300474162107271438029222620086",
+"010527691044447729596127150108", "742822904991333205419603623270"};
+	  vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 
+	string tens_[] = {"029421809872798033258029765788", "705135039569772524273274786652",
+"170567418260893393020344098265", "401043354947659563658581268242",
+"746709065616595245635350557925", "739570024549618413776557843034",
+"184597012262496958610853505745", "689811400727818703807051112784", 
+"894453010121164288965541305235", "323145029073008946088869964941", 
+"834269564400729646453274750586", "538976762970745472202055589093", 
+"765511399939087047106252621388", "906733295711605356366138410423", 
+"107653940551700559321642810836", "428402693021051075533830345295", 
+"386782660475155103347385287948", "936626025836194580089064628716", 
+"718522629491464055045890912121", "370656945845300237607868352243", 
+"951908186614186444840337711498", "535178875249889835014025850038", 
+"505970047705717604298603983975", "484398304612602344941130624527", 
+"048342694079170795987835013947", "860331019262176299872846206272", 
+"549663926438975145562538360932", "329735455392841851511474791078", 
+"711755200061373546828858448100", "778808866574640894148527759780"};
+	  vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); 
+	string ones_[] = {"050738147930236727719964251439", "804492562859282318664226330103", 
+"610197568193830684654773608216", "279000416545607314567843085541", 
+"782201171759873927350740022455", "043370803444176631019883186675", 
+"566092086050401228622782761449", "469598907881602996036692882305", 
+"116923500417992303845370254124", "796876115092839169954790509461", 
+"783836410405270687557924090071", "095144151150833738671751747749", 
+"354474585664039135189964700948", "328968176148004939648962631420", 
+"829651915384290848347221555092", "170980383407813034573738951375", 
+"728655435703349509419725538350", "121896684176286430427852435647", 
+"315710894574884960021671476788", "592177839598531202003634382961", 
+"876587919610157913350259498196", "505517243779897451333006271744", 
+"618607877753891664471800511372", "826358757330233811836040764274", 
+"206641252044293046424432092833", "704519364781672964993499009545", 
+"624793571592392775564426440338", "571938479010503551295729304078", 
+"077967252884369103891335711508", "870185204806328841827105139840"};
+	  vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); 
+	int _ = 39896; 
+END
+/*
+CASE(8)
+	string thousands_[] = ;
+	  vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/sizeof(*thousands_)); 
+	string hundreds_[] = ;
+	  vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 
+	string tens_[] = ;
+	  vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); 
+	string ones_[] = ;
+	  vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); 
+	int _ = ; 
+END
+CASE(9)
+	string thousands_[] = ;
+	  vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/sizeof(*thousands_)); 
+	string hundreds_[] = ;
+	  vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 
+	string tens_[] = ;
+	  vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); 
+	string ones_[] = ;
+	  vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); 
+	int _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/TCO12-2C-U/1B.cpp
Index: SRM/TCO12-2C-U/1B.cpp
==================================================================
--- SRM/TCO12-2C-U/1B.cpp
+++ SRM/TCO12-2C-U/1B.cpp
@@ -0,0 +1,179 @@
+#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 <memory>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+template<typename T=LL>
+struct FenwickTree
+{
+	vector<T> x;
+	FenwickTree(size_t n) : x(n) {}
+
+	void incr( int k, const T& a ) { // z[k] += a;
+		for(; k < x.size(); k|=k+1)
+			x[k] += a;
+	}
+	T sum(int i, int j) { // Sigma z[i,j) excl.
+		return sum_impl(j-1) - sum_impl(i-1);
+	}
+	T sum_impl(int j) { // Sigma z[0,j] incl.
+		T v = T();
+		for(; j>=0; j=(j&(j+1))-1)
+			v += x[j];
+		return v;
+	}
+};
+
+template<typename T>
+std::vector<int> compress(std::vector<T>& xs)
+{
+	std::vector< pair<T,int> > xi;
+	for(int i=0; i<xs.size(); ++i)
+		xi.push_back( make_pair(xs[i], i) );
+	sort(xi.begin(), xi.end());
+
+	std::vector<int> result(xs.size());
+	for(int k=0; k<xi.size(); ++k)
+		result[xi[k].second] = k;
+	return result;
+}
+
+class ThreePoints { public:
+	long long countColoring(int N,
+		int xzero, int xmul, int xadd, int xmod,
+		int yzero, int ymul, int yadd, int ymod)
+	{
+		vector<int> x(N), y(N);
+		x[0] = xzero; for(int i=1; i<N; ++i) x[i] = (x[i-1] * LL(xmul) + xadd) % xmod;
+		y[0] = yzero; for(int i=1; i<N; ++i) y[i] = (y[i-1] * LL(ymul) + yadd) % ymod;
+		x = compress(x);
+		y = compress(y);
+
+		vector< pair<int,int> > y_desc;
+		for(int i=0; i<N; ++i)
+			y_desc.push_back(make_pair(y[i], x[i]));
+		sort(y_desc.rbegin(), y_desc.rend());
+
+		LL result = 0;
+		FenwickTree<> p(N), sp(N);
+		for(int i=0; i<N; ++i) {
+			const int x = y_desc[i].second;
+			LL sp_  = p.sum(x+1, N);
+			LL ssp_ = sp.sum(x+1, N);
+			p.incr(x, 1);
+			sp.incr(x, sp_);
+			result += sp_*(sp_-1)/2 - ssp_;
+		}
+		return result;
+	}
+};
+
+// 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 long long& Expected, const long long& 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(_, ThreePoints().countColoring(N, xzero, xmul, xadd, xmod, yzero, ymul, yadd, ymod));}
+int main(){
+
+CASE(0)
+	int N = 9; 
+	int xzero = 3; 
+	int xmul = 8; 
+	int xadd = 6; 
+	int xmod = 11; 
+	int yzero = 5; 
+	int ymul = 7; 
+	int yadd = 8; 
+	int ymod = 11; 
+	long long _ = 8LL; 
+END
+CASE(1)
+	int N = 4; 
+	int xzero = 9; 
+	int xmul = 6; 
+	int xadd = 8; 
+	int xmod = 10; 
+	int yzero = 4; 
+	int ymul = 8; 
+	int yadd = 5; 
+	int ymod = 10; 
+	long long _ = 2LL; 
+END
+CASE(2)
+	int N = 20; 
+	int xzero = 30; 
+	int xmul = 3; 
+	int xadd = 71; 
+	int xmod = 100; 
+	int yzero = 78; 
+	int ymul = 12; 
+	int yadd = 50; 
+	int ymod = 100; 
+	long long _ = 263LL; 
+END
+CASE(3)
+	int N = 300000; 
+	int xzero = 99097861; 
+	int xmul = 102766912; 
+	int xadd = 95284952; 
+	int xmod = 123456789; 
+	int yzero = 443104491; 
+	int ymul = 971853214; 
+	int yadd = 569775557; 
+	int ymod = 987654321; 
+	long long _ = 749410681185726LL; 
+END
+/*
+CASE(4)
+	int N = ; 
+	int xzero = ; 
+	int xmul = ; 
+	int xadd = ; 
+	int xmod = ; 
+	int yzero = ; 
+	int ymul = ; 
+	int yadd = ; 
+	int ymod = ; 
+	long long _ = LL; 
+END
+CASE(5)
+	int N = ; 
+	int xzero = ; 
+	int xmul = ; 
+	int xadd = ; 
+	int xmod = ; 
+	int yzero = ; 
+	int ymul = ; 
+	int yadd = ; 
+	int ymod = ; 
+	long long _ = LL; 
+END
+*/
+}
+// END CUT HERE

Index: lib/dataStructure/fenwickTree.cpp
==================================================================
--- lib/dataStructure/fenwickTree.cpp
+++ lib/dataStructure/fenwickTree.cpp
@@ -2,29 +2,28 @@
 // Fenwick Tree
 //   O(log N) per each operation
 //
 // Verified by
 //   - SRM424 Div1 LV3
+//   - TCO12 R2C LV2
 //-------------------------------------------------------------
 
-template<typename T = LL>
+template<typename T=LL>
 struct FenwickTree
 {
 	vector<T> x;
-	FenwickTree(size_t n, const T& v = T()) : x(n, v) {}
+	FenwickTree(size_t n) : x(n) {}
 
 	void incr( int k, const T& a ) { // z[k] += a;
 		for(; k < x.size(); k|=k+1)
 			x[k] += a;
 	}
-
-	T sum(int i, int j) { // z[i]+...+z[j] : inclusive
-		if(i)
-			return sum(0, j) - sum(0, i-1);
-		else {
-			T v = T();
-			for(; j>=0; j=(j&(j+1))-1)
-				v += x[j];
-			return v;
-		}
+	T sum(int i, int j) { // Sigma z[i,j) excl.
+		return sum_impl(j-1) - sum_impl(i-1);
+	}
+	T sum_impl(int j) { // Sigma z[0,j] incl.
+		T v = T();
+		for(; j>=0; j=(j&(j+1))-1)
+			v += x[j];
+		return v;
 	}
 };

Index: lib/dataStructure/segmentTree.cpp
==================================================================
--- lib/dataStructure/segmentTree.cpp
+++ lib/dataStructure/segmentTree.cpp
@@ -26,16 +26,16 @@
 			for(int i=0; i<N; ++i)
 				CalcMidNode(tree.size()-1, i);
 		}
 	}
 
-	Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n)
+	Node Query(int s, int e) { // compute h( seq[s,e) ) :  O(log n)
 		return QueryRec(s, e, tree.size()-1, 0, tree[0].size());
 	}
 
 	template<typename Value>
-	void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n�E|e-s|)
+	void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n |e-s|)
 		SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size());
 	}
 
 private:
 	void CalcMidNode(int lv, int idx)

ADDED   lib/typical/coordinate_compression.cpp
Index: lib/typical/coordinate_compression.cpp
==================================================================
--- lib/typical/coordinate_compression.cpp
+++ lib/typical/coordinate_compression.cpp
@@ -0,0 +1,17 @@
+// Convert a list of distinct elements to [0..N), preserving the original order.
+// O(N log N), but doesn't incur the overhead of std::map.
+// Tested: TCO 2012 R2C Mid
+
+template<typename T>
+std::vector<int> compress(std::vector<T>& xs)
+{
+	std::vector< pair<T,int> > xi;
+	for(int i=0; i<xs.size(); ++i)
+		xi.push_back( make_pair(xs[i], i) );
+	sort(xi.begin(), xi.end());
+
+	std::vector<int> result(xs.size());
+	for(int k=0; k<xi.size(); ++k)
+		result[xi[k].second] = k;
+	return result;
+}