6efd022c37 2013-05-11        kinaba: #include <iostream>
6efd022c37 2013-05-11        kinaba: #include <sstream>
6efd022c37 2013-05-11        kinaba: #include <iomanip>
6efd022c37 2013-05-11        kinaba: #include <vector>
6efd022c37 2013-05-11        kinaba: #include <string>
6efd022c37 2013-05-11        kinaba: #include <map>
6efd022c37 2013-05-11        kinaba: #include <set>
6efd022c37 2013-05-11        kinaba: #include <algorithm>
6efd022c37 2013-05-11        kinaba: #include <numeric>
6efd022c37 2013-05-11        kinaba: #include <iterator>
6efd022c37 2013-05-11        kinaba: #include <functional>
6efd022c37 2013-05-11        kinaba: #include <complex>
6efd022c37 2013-05-11        kinaba: #include <queue>
6efd022c37 2013-05-11        kinaba: #include <stack>
6efd022c37 2013-05-11        kinaba: #include <cmath>
6efd022c37 2013-05-11        kinaba: #include <cassert>
6efd022c37 2013-05-11        kinaba: using namespace std;
6efd022c37 2013-05-11        kinaba: typedef long long LL;
6efd022c37 2013-05-11        kinaba: typedef long double LD;
6efd022c37 2013-05-11        kinaba: typedef complex<LD> CMP;
6efd022c37 2013-05-11        kinaba: 
6efd022c37 2013-05-11        kinaba: static const unsigned MODVAL = 1000000007;
6efd022c37 2013-05-11        kinaba: 
6efd022c37 2013-05-11        kinaba: class WolfInZooDivOne { public:
6efd022c37 2013-05-11        kinaba: 	int count(int N, vector <string> L_, vector <string> R_)
6efd022c37 2013-05-11        kinaba: 	{
6efd022c37 2013-05-11        kinaba: 		vector<int> L, R;
6efd022c37 2013-05-11        kinaba: 		{
6efd022c37 2013-05-11        kinaba: 			stringstream sin(accumulate(L_.begin(), L_.end(), string()));
6efd022c37 2013-05-11        kinaba: 			for(int s; sin>>s;) L.push_back(s);
6efd022c37 2013-05-11        kinaba: 		}
6efd022c37 2013-05-11        kinaba: 		{
6efd022c37 2013-05-11        kinaba: 			stringstream sin(accumulate(R_.begin(), R_.end(), string()));
6efd022c37 2013-05-11        kinaba: 			for(int s; sin>>s;) R.push_back(s+1);
6efd022c37 2013-05-11        kinaba: 		}
6efd022c37 2013-05-11        kinaba: 
6efd022c37 2013-05-11        kinaba: 		set< pair<int,int> > LR;
6efd022c37 2013-05-11        kinaba: 		for(int i=0; i<L.size(); ++i)
6efd022c37 2013-05-11        kinaba: 			LR.insert(make_pair(L[i], R[i]));
6efd022c37 2013-05-11        kinaba: 
6efd022c37 2013-05-11        kinaba: 		vector< pair<int,int> > LR_imp;
6efd022c37 2013-05-11        kinaba: 		for(set< pair<int,int> >::iterator it=LR.begin(); it!=LR.end(); ++it) {
6efd022c37 2013-05-11        kinaba: 			bool important = true;
6efd022c37 2013-05-11        kinaba: 			for(set< pair<int,int> >::iterator kt=LR.begin(); kt!=LR.end(); ++kt)
6efd022c37 2013-05-11        kinaba: 				if(it != kt && kt->first<=it->first && it->second<=kt->second)
6efd022c37 2013-05-11        kinaba: 					important = false;
6efd022c37 2013-05-11        kinaba: 			if(important)
6efd022c37 2013-05-11        kinaba: 				LR_imp.push_back(*it);
6efd022c37 2013-05-11        kinaba: 		}
6efd022c37 2013-05-11        kinaba: 
6efd022c37 2013-05-11        kinaba: 		return solve(N, LR_imp);
6efd022c37 2013-05-11        kinaba: 	}
6efd022c37 2013-05-11        kinaba: 
6efd022c37 2013-05-11        kinaba: 	int solve(int N, const vector< pair<int,int> >& LR)
6efd022c37 2013-05-11        kinaba: 	{
6efd022c37 2013-05-11        kinaba: 		memo = vector<vector<vector<int> > >(N,
6efd022c37 2013-05-11        kinaba: 			vector<vector<int> >(LR.size()+1, vector<int>(LR.size()+1, -1)));
6efd022c37 2013-05-11        kinaba: 		return rec(0, N, LR, 0, 0, 0, 0);
6efd022c37 2013-05-11        kinaba: 	}
6efd022c37 2013-05-11        kinaba: 
6efd022c37 2013-05-11        kinaba: 	vector<vector<vector<int> > > memo;
6efd022c37 2013-05-11        kinaba: 	int rec(int i, const int N, const vector< pair<int,int> >& LR, int end_of_past, int end_of_two, int end_of_one,
6efd022c37 2013-05-11        kinaba: 		int end_of_zero)
6efd022c37 2013-05-11        kinaba: 	{
6efd022c37 2013-05-11        kinaba: 		if(i == N)
6efd022c37 2013-05-11        kinaba: 			return 1;
6efd022c37 2013-05-11        kinaba: 		int& me = memo[i][end_of_two][end_of_one];
6efd022c37 2013-05-11        kinaba: 		if(me != -1)
6efd022c37 2013-05-11        kinaba: 			return me;
6efd022c37 2013-05-11        kinaba: 
6efd022c37 2013-05-11        kinaba: 		int ez = end_of_zero;
6efd022c37 2013-05-11        kinaba: 		while(ez<LR.size() && LR[ez].first<=i)
6efd022c37 2013-05-11        kinaba: 			++ez;
6efd022c37 2013-05-11        kinaba: 		int ep = end_of_past;
6efd022c37 2013-05-11        kinaba: 		while(ep<ez && LR[ep].second<=i)
6efd022c37 2013-05-11        kinaba: 			++ep;
6efd022c37 2013-05-11        kinaba: 
6efd022c37 2013-05-11        kinaba: 		// do not place wolf at i.
6efd022c37 2013-05-11        kinaba: 		int total = rec(i+1, N, LR, ep, max(ep,end_of_two), max(ep,end_of_one), ez);
6efd022c37 2013-05-11        kinaba: 
6efd022c37 2013-05-11        kinaba: 		// place wolf at i.
6efd022c37 2013-05-11        kinaba: 		if(ep >= end_of_two) {
6efd022c37 2013-05-11        kinaba: 			int e1 = max(ep, end_of_one);
6efd022c37 2013-05-11        kinaba: 			int e2 = max(ep, end_of_two);
6efd022c37 2013-05-11        kinaba: 			while(e2<e1 && i<LR[e2].second)
6efd022c37 2013-05-11        kinaba: 				++e2;
6efd022c37 2013-05-11        kinaba: 			while(e1<ez && i<LR[e1].second)
6efd022c37 2013-05-11        kinaba: 				++e1;
6efd022c37 2013-05-11        kinaba: 			total += rec(i+1, N, LR, ep, e2, e1, ez);
6efd022c37 2013-05-11        kinaba: 		}
6efd022c37 2013-05-11        kinaba: 		return me = (total % MODVAL);
6efd022c37 2013-05-11        kinaba: 	}
6efd022c37 2013-05-11        kinaba: };
6efd022c37 2013-05-11        kinaba: 
6efd022c37 2013-05-11        kinaba: // BEGIN CUT HERE
6efd022c37 2013-05-11        kinaba: #include <ctime>
6efd022c37 2013-05-11        kinaba: double start_time; string timer()
6efd022c37 2013-05-11        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
6efd022c37 2013-05-11        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
6efd022c37 2013-05-11        kinaba:  { os << "{ ";
6efd022c37 2013-05-11        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
6efd022c37 2013-05-11        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
6efd022c37 2013-05-11        kinaba: void verify_case(const int& Expected, const int& Received) {
6efd022c37 2013-05-11        kinaba:  bool ok = (Expected == Received);
6efd022c37 2013-05-11        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
6efd022c37 2013-05-11        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
6efd022c37 2013-05-11        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
6efd022c37 2013-05-11        kinaba: #define END	 verify_case(_, WolfInZooDivOne().count(N, L, R));}
6efd022c37 2013-05-11        kinaba: int main(){
6efd022c37 2013-05-11        kinaba: 
6efd022c37 2013-05-11        kinaba: CASE(0)
6efd022c37 2013-05-11        kinaba: 	int N = 5;
6efd022c37 2013-05-11        kinaba: 	string L_[] = {"0"};
6efd022c37 2013-05-11        kinaba: 	  vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
6efd022c37 2013-05-11        kinaba: 	string R_[] = {"4"};
6efd022c37 2013-05-11        kinaba: 	  vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
6efd022c37 2013-05-11        kinaba: 	int _ = 16;
6efd022c37 2013-05-11        kinaba: END
6efd022c37 2013-05-11        kinaba: CASE(1)
6efd022c37 2013-05-11        kinaba: 	int N = 5;
6efd022c37 2013-05-11        kinaba: 	string L_[] = {"0 1"};
6efd022c37 2013-05-11        kinaba: 	  vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
6efd022c37 2013-05-11        kinaba: 	string R_[] = {"2 4"};
6efd022c37 2013-05-11        kinaba: 	  vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
6efd022c37 2013-05-11        kinaba: 	int _ = 21;
6efd022c37 2013-05-11        kinaba: END
6efd022c37 2013-05-11        kinaba: CASE(2)
6efd022c37 2013-05-11        kinaba: 	int N = 10;
6efd022c37 2013-05-11        kinaba: 	string L_[] = {"0 4 2 7"};
6efd022c37 2013-05-11        kinaba: 	  vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
6efd022c37 2013-05-11        kinaba: 	string R_[] = {"3 9 5 9"};
6efd022c37 2013-05-11        kinaba: 	  vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
6efd022c37 2013-05-11        kinaba: 	int _ = 225;
6efd022c37 2013-05-11        kinaba: END
6efd022c37 2013-05-11        kinaba: CASE(3)
6efd022c37 2013-05-11        kinaba: 	int N = 100;
6efd022c37 2013-05-11        kinaba: 	string L_[] = {"0 2 2 7 10 1","3 16 22 30 33 38"," 42 44 49 51 57 60 62"," 65 69 72 74 77 7","8 81 84 88 91 93 96"};
6efd022c37 2013-05-11        kinaba: 	  vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
6efd022c37 2013-05-11        kinaba: 	string R_[] = {"41 5 13 22 12 13 ","33 41 80 47 40 ","4","8 96 57 66 ","80 60 71 79"," 70 77 ","99"," 83 85 93 88 89 97 97 98"};
6efd022c37 2013-05-11        kinaba: 	  vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
6efd022c37 2013-05-11        kinaba: 	int _ = 6419882;
6efd022c37 2013-05-11        kinaba: END
6efd022c37 2013-05-11        kinaba: /*
6efd022c37 2013-05-11        kinaba: CASE(4)
6efd022c37 2013-05-11        kinaba: 	int N = ;
6efd022c37 2013-05-11        kinaba: 	string L_[] = ;
6efd022c37 2013-05-11        kinaba: 	  vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
6efd022c37 2013-05-11        kinaba: 	string R_[] = ;
6efd022c37 2013-05-11        kinaba: 	  vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
6efd022c37 2013-05-11        kinaba: 	int _ = ;
6efd022c37 2013-05-11        kinaba: END
6efd022c37 2013-05-11        kinaba: CASE(5)
6efd022c37 2013-05-11        kinaba: 	int N = ;
6efd022c37 2013-05-11        kinaba: 	string L_[] = ;
6efd022c37 2013-05-11        kinaba: 	  vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
6efd022c37 2013-05-11        kinaba: 	string R_[] = ;
6efd022c37 2013-05-11        kinaba: 	  vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
6efd022c37 2013-05-11        kinaba: 	int _ = ;
6efd022c37 2013-05-11        kinaba: END
6efd022c37 2013-05-11        kinaba: */
6efd022c37 2013-05-11        kinaba: }
6efd022c37 2013-05-11        kinaba: // END CUT HERE